En familj av grafer sägs ha en begränsad förlängning om alla dess avgränsade djup-molor är grafglesa . Många naturliga familjer av glesa grafer har begränsad förlängning. En relaterad men starkare egenskap, polynomförlängning , är ekvivalent med förekomsten av partitionssatser för dessa familjer. Familjer med dessa egenskaper har effektiva algoritmer för problem som inkluderar det isomorfa subgrafproblemet och modelltestning för första ordningens grafteori.
Djupet t moll för en graf G definieras som den graf som bildas av G genom att sammandra uppsättningen subgrafer med radie t som inte har några gemensamma hörn och ta bort de återstående hörnen. En familj av grafer har en avgränsad förlängning om det finns en funktion f så att förhållandet mellan antalet kanter och antalet hörn inte överstiger f ( t ) för varje mindre av djupet t i en graf i familjen. 1] .
En annan definition av begränsade förlängningsklasser är att alla minderåriga med begränsat djup har ett kromatiskt tal , begränsat av någon funktion av t [1] , eller så har en given familj ett begränsat värde på den topologiska parametern . En sådan parameter är en grafinvariant , monoton med avseende på subgraftagning, så att värdet på parametern endast kan ändras på ett kontrollerat sätt när grafen delas, och av parametervärdets avgränsning följer att grafen har avgränsat degeneration [2] .
En mer rigorös föreställning är polynomförlängningen , vilket betyder att funktionen f som används för att begränsa kanttätheten för bifogade djupled är polynom . Om en ärvd familj av grafer uppfyller partitionssatsen , som säger att varje graf med n hörn i familjen kan delas upp i två delar som innehåller högst n /2 hörn genom att ta bort O ( n c ) hörn för någon konstant c < 1, då har denna familj nödvändigtvis en polynomförlängning. Omvänt har grafer med polynomförlängning satser med en sublinjär separator [3] .
Eftersom det finns ett samband mellan separatorer och förlängning, har alla små slutna graffamiljer , inklusive familjen av plana grafer , en polynomförlängning. Detsamma gäller för 1-planära grafer , och mer generellt för grafer som kan bäddas in i ytor av begränsat släkte med ett begränsat antal korsningar per kant, på samma sätt som stränggrafer utan bicliques , eftersom det finns separatorsatser för dem , liknande satserna för plana grafer [4] [5] [6] . I euklidiska utrymmen av högre dimensioner uppfyller skärningsdiagrammen för system av bollar med egenskapen att vilken punkt som helst i utrymmet täcks av ett begränsat antal bollar också partitionssatser [7] , vilket innebär att det finns en polynomförlängning.
Även om grafer med avgränsad bokbredd inte innehåller sublinjära separatorer [8] , har de också avgränsade förlängningar [9] . Klassen av grafer med begränsad förlängning inkluderar grafer med begränsad grad [10] , slumpmässiga grafer med begränsad medelgrad i Erdős-Rényi-modellen [11] och grafer med ett begränsat antal köer [2] [12] .
Ett exempel på subgrafisomorfismproblemet , där målet är att hitta en graf med begränsad storlek som är en subgraf till en större graf vars storlek inte är begränsad, kan lösas i linjär tid om den större grafen tillhör en familj av grafer med avgränsad förlängning. Detsamma gäller för att hitta klick med fast storlek , att hitta dominerande uppsättningar med fast storlek , eller mer allmänt, testa egenskaper som kan uttryckas med en formel för begränsad storlek i graflogik av första ordningen 13] [14] .
För polynomförlängningsgrafer finns det ungefärliga polynomtidsscheman för det uppsättningstäckande problemet , det maximala oberoende uppsättningsproblemet , det dominerande uppsättningsproblemet och några andra relaterade optimeringsproblem [15] .