Begränsningsdiagram (layout)
I vissa uppgifter för design av integrerade kretsar uppstår en nödvändighet att optimera placeringen av icke-överlappande objekt i planet. I allmänhet är detta problem extremt svårt, och för att hantera det med datoralgoritmer görs vissa antaganden om tillåtna placeringar och om operationer som är tillåtna i placeringsmodifieringar. Restriktionsgrafer fångar begränsningarna för relativa rörelser för objekten som placeras i planet. Dessa grafer, samtidigt som de delar en gemensam idé, har olika definition, beroende på en viss designuppgift eller dess modell.
Golvplanering
I golvplanering är modellen för en planlösning för en integrerad krets en uppsättning isotetiska rektanglar som kallas "block" inom en större rektangel som kallas "gräns" (t.ex. " chipgräns ", " cellgräns ").
En möjlig definition av begränsningsgrafer är följande. Begränsningsgrafen för en given planlösning är en riktad graf där vertexuppsättningen är uppsättningen av planritningsblock och det finns en kant från block b1 till b2 (kallad horisontell begränsning), om b1 är helt till vänster om b2 och det finns en kant från block b1 till b2 (kallad vertikal begränsning), om b1 är helt under b2.
Om endast horisontella begränsningar beaktas, får man den horisontella begränsningsgrafen . Om endast vertikala begränsningar beaktas, får man den vertikala begränsningsgrafen .
Enligt denna definition kan begränsningsgrafen ha så många som kanter, där n är antalet block. Därför övervägs andra, mindre täta begränsningsgrafer. Den horisontella synlighetsgrafen är en horisontell begränsningsgraf där den horisontella begränsningen mellan två block endast existerar om det finns ett horisontellt linjesegment som förbinder de två blocken och inte skär några andra block. Med andra ord är ett block ett potentiellt "omedelbart hinder" för att flytta ett annat horisontellt. Den vertikala synlighetsgrafen definieras på liknande sätt.
Kanaldirigering
Kanaldirigering är problemet med dirigering av en uppsättning nät N som har fasta terminaler på två motsatta sidor av en rektangel ("kanal"). I detta sammanhang är den horisontella begränsningsgrafen den oriktade grafen med vertexuppsättning N och två nät är förbundna med en kant om och endast om horisontella segment av routingen måste överlappa varandra. I det givna exemplet är det bara nät 5 och 6 som inte har en horisontell begränsning mellan sig. Den vertikala begränsningsgrafen är den riktade grafen med vertexuppsättning N och två nät är förbundna med en kant om och endast om det finns två stift från olika nät på samma vertikala linje och kanten är riktad från nätet med stift på den övre kanten av kanalen. Denna riktning innebär att detta nät måste dras på ett horisontellt spår ovanför det andra nätets horisontella spår. I det givna exemplet har endast nät 1 och 3 en vertikal begränsning.