Se spune că o familie de grafice are o extensie mărginită dacă toate elementele minore ale adâncimii mărginite sunt rare în graf . Multe familii naturale de grafice rare au o extensie limitată. O proprietate înrudită, dar mai puternică, extensia polinomială , este echivalentă cu existența teoremelor de partiție pentru aceste familii. Familiile cu aceste proprietăți au algoritmi eficienți pentru probleme care includ problema subgrafului izomorf și testarea modelului pentru teoria grafurilor de ordinul întâi.
Adâncimea t minor a unui grafic G este definită ca graficul format din G prin contractarea setului de subgrafe de rază t care nu au vârfuri comune și eliminând vârfurile rămase. O familie de grafuri are o extensie mărginită dacă există o funcție f astfel încât, pentru orice minor de adâncime t al unui graf din familie, raportul dintre numărul de muchii și numărul de vârfuri să nu depășească f ( t ) [ 1] .
O altă definiție a claselor de extensie mărginită este aceea că toți minorii de adâncime mărginită au un număr cromatic , mărginit de o funcție a lui t [1] , sau o familie dată are o valoare mărginită a parametrului topologic . Un astfel de parametru este un grafic invariant , monoton în ceea ce privește luarea subgrafului, astfel încât valoarea parametrului se poate schimba doar într-un mod controlat atunci când graficul este împărțit, iar din limitele valorii parametrului rezultă că graficul a fost mărginit. degenerare [2] .
O noțiune mai riguroasă este extensia polinomială , ceea ce înseamnă că funcția f folosită pentru a constrânge densitatea marginilor minorilor cu adâncime mărginită este polinomială . Dacă o familie moștenită de grafice satisface teorema partiției , care afirmă că orice graf cu n vârfuri din familie poate fi împărțit în două părți care conțin cel mult n /2 vârfuri prin eliminarea O ( n c ) vârfuri pentru o constantă c < 1, atunci această familie are în mod necesar o extensie polinomială. Dimpotrivă, graficele cu extensie polinomială au teoreme cu separator subliniar [3] .
Deoarece există o conexiune între separatori și extensie, orice familie minoră-închisă de grafuri , inclusiv familia grafurilor plane , are o extensie polinomială. Același lucru este valabil și pentru graficele 1-planare și, mai general, pentru graficele care pot fi încorporate în suprafețe de gen mărginit cu un număr mărginit de încrucișări pe muchie, în același mod ca și graficele cu șiruri fără biclicuri , deoarece există teoreme de separare pentru ele. , similar cu teoremele pentru grafurile plane [4] [5] [6] . În spațiile euclidiene de dimensiuni mai mari , graficele de intersecție ale sistemelor de bile cu proprietatea că orice punct din spațiu este acoperit de un număr limitat de bile satisfac și teoremele de partiție [7] , ceea ce presupune existența unei extensii polinomiale.
Deși graficele cu lățime de carte mărginită nu conțin separatori subliniari [8] , ele au și extensii mărginite [9] . Clasa de grafice cu extensie mărginită include grafice de grad mărginit [10] , grafice aleatoare de grad mediu mărginit în modelul Erdős-Rényi [11] , și grafice cu un număr mărginit de cozi [2] [12] .
O instanță a problemei izomorfismului subgrafului , în care scopul este de a găsi un grafic de mărime mărginită care este un subgraf al unui grafic mai mare a cărui dimensiune nu este mărginită, poate fi rezolvată în timp liniar dacă graficul mai mare aparține unei familii de grafice cu extensie mărginită. Același lucru este valabil și pentru găsirea clicurilor de dimensiune fixă , găsirea mulțimilor dominante de dimensiune fixă sau, mai general, testarea proprietăților care pot fi exprimate printr-o formulă de mărime mărginită în logica grafică de ordinul întâi 13] [14] .
Pentru graficele de extensie polinomială, există scheme de timp polinomiale aproximative pentru problema de acoperire a mulțimii , problema mulțimii independente maxime , problema mulțimii dominante și alte probleme de optimizare înrudite [15] .