En familie af grafer siges at have en afgrænset forlængelse, hvis alle dens afgrænsede dybde-minorer er graf sparsomme . Mange naturlige familier af sparsomme grafer har begrænset udvidelse. En beslægtet, men stærkere egenskab, polynomial extension , svarer til eksistensen af partitionsteoremer for disse familier. Familier med disse egenskaber har effektive algoritmer til problemer, der inkluderer det isomorfe subgrafproblem og modeltestning for første-ordens grafteori.
Dybden t minor af en graf G er defineret som grafen dannet ud fra G ved at kontrahere sættet af undergrafer med radius t , der ikke har fælles toppunkter , og fjerne de resterende toppunkter. En familie af grafer har en afgrænset forlængelse, hvis der eksisterer en funktion f , således at forholdet mellem antallet af kanter og antallet af hjørner ikke overstiger f ( t ) for enhver mindre dybde t af en graf i familien . 1] .
En anden definition af afgrænsede udvidelsesklasser er, at alle mindretal med begrænset dybde har et kromatisk tal , afgrænset af en funktion af t [1] , eller en given familie har en afgrænset værdi af den topologiske parameter . En sådan parameter er en grafinvariant , monoton med hensyn til subgraftagning, således at værdien af parameteren kun kan ændres på en kontrolleret måde, når grafen er opdelt, og af parameterværdiens afgrænsning følger, at grafen er afgrænset degeneration [2] .
En mere stringent forestilling er polynomial-udvidelsen , hvilket betyder, at funktionen f , der bruges til at begrænse kanttætheden af afgrænsede dybder, er polynomium . Hvis en nedarvet familie af grafer opfylder partitionssætningen , som siger, at enhver graf med n toppunkter i familien kan opdeles i to dele indeholdende højst n /2 toppunkter ved at fjerne O ( n c ) toppunkter for en konstant c < 1, så har denne familie nødvendigvis en polynomisk forlængelse. Omvendt har grafer med polynomisk forlængelse sætninger med en sublineær separator [3] .
Fordi der er en forbindelse mellem separatorer og udvidelse, har enhver mindre-lukket familie af grafer , inklusive familien af plane grafer , en polynomiel udvidelse. Det samme gælder for 1-plane grafer , og mere generelt for grafer, der kan indlejres i overflader af afgrænset slægt med et begrænset antal krydsninger pr. kant, på samme måde som strenggrafer uden bicliques , da der er separatorsætninger for dem , svarende til sætningerne for plane grafer [4] [5] [6] . I euklidiske rum af højere dimensioner opfylder skæringsgraferne for systemer af kugler med den egenskab, at ethvert punkt i rummet er dækket af et begrænset antal kugler, også partitionsteoremer [7] , hvilket indebærer eksistensen af en polynomiel forlængelse.
Selvom grafer med begrænset bogbredde ikke indeholder sublineære separatorer [8] , har de også afgrænsede udvidelser [9] . Klassen af grafer med afgrænset forlængelse omfatter grafer med afgrænset grad [10] , tilfældige grafer med afgrænset gennemsnitsgrad i Erdős-Rényi-modellen [11] og grafer med et begrænset antal køer [2] [12] .
Et eksempel på subgraph isomorphism problem , hvor målet er at finde en graf af begrænset størrelse, der er en subgraf af en større graf, hvis størrelse ikke er begrænset, kan løses i lineær tid, hvis den større graf tilhører en familie af grafer med afgrænset forlængelse. Det samme gælder for at finde kliker med fast størrelse , finde dominerende sæt med fast størrelse eller mere generelt test af egenskaber, der kan udtrykkes med en afgrænset størrelsesformel i førsteordens graflogik 13] [14] .
For polynomielle forlængelsesgrafer er der tilnærmede polynomielle tidsskemaer for mængden, der dækker problemet , det maksimale uafhængige sætproblem, det dominerende sætproblem og nogle andre relaterede optimeringsproblemer [15] .