Planar separatorsats

I grafteorin är planseparatorsatsen en form av isoperimetrisk olikhet för plana grafer , som säger att vilken plan graf som helst kan delas upp i mindre bitar genom att ta bort ett litet antal hörn . Närmare bestämt kan borttagningen av $O({\sqrt {n}})$ hörn från en n -vertexgraf (där O :et anropar stor O-notation ) dela upp grafen i disjunkta subgrafer som var och en har högst $2n/3$ hörn.

En svagare form av separatorsatsen med $O({\sqrt {n}}\log ^{3/2}n)$ hörn i separatorn istället för $O({\sqrt {n}})$ bevisades ursprungligen av Ungar (1951) , och formen med den snäva asymptotiska bunden på separatorstorleken bevisades först av Lipton & Tarjan (1979) . Sedan deras arbete har separatorsatsen bevisats på flera olika sätt, konstanten i $O({\sqrt {n}})$ termen i satsen har förbättrats, och den har utökats till vissa klasser av icke-planära grafer.

Upprepad tillämpning av separatorsatsen producerar en separatorhierarki som kan ha formen av antingen en trädupplösning eller en grenupplösning av grafen. Separatorhierarkier kan användas för att skapa effektiva dividera och erövra algoritmer för plana grafer, och dynamisk programmering på dessa hierarkier kan användas för att ta fram exponentiella tids- och algoritmer med fasta parametrar för att lösa NP-hårda optimeringsproblem på dessa grafer. Separatorhierarkier kan också användas i kapslad dissektion , en effektiv variant av Gaussisk eliminering för att lösa glesa system av linjära ekvationer som härrör från finita elementmetoder .

Bortom plana grafer, har separatorsatser tillämpats på andra klasser av grafer inklusive grafer som exkluderar en fast moll , närmaste grannegrafer och finita elementmaskor . Förekomsten av en separatorsats för en klass av grafer kan formaliseras och kvantifieras genom begreppen trädbredd och polynomexpansion .

Uttalande av satsen

Som det brukar sägas, säger separatorsatsen att det i varje $n$ -vertex plan graf $G=(V,E)$ finns en partition av hörnen av $G$ i tre uppsättningar $A$ , $S$ och $B$ , så att var och en av $A$ och $B$ har högst $2n/3$ hörn, $S$ har $O({\sqrt {n}})$ hörn, och det finns inga kanter med en ändpunkt i $A$ och en slutpunkt i $B$ . Det krävs inte att $A$ eller $B$ bildar anslutna subgrafer av $G$ . $S$ kallas separatorn för denna partition.

En ekvivalent formulering är att kanterna på valfri $n$ -vertex plan graf $G$ kan delas in i två kant-disjunkte subgrafer $G_{1}$ och $G_{2}$ på ett sådant sätt att båda subgraferna har minst $n/3}$$) {\displaystyle O({ \sqrt {n}})}$ hörn och så att skärningspunkten mellan vertexmängderna för de två subgraferna har hörn i den. En sådan partition är känd som en separation . Om en separation ges, bildar skärningspunkten mellan vertexmängderna en separator, och de hörn som hör till en subgraf men inte den andra bildar separerade delmängder som var och en har högst 2 n / 3 {\displaystyle $hörn$ . I den andra riktningen, om man ges en partition i tre uppsättningar $A$ , $S$ och $B$ som uppfyller villkoren för planseparatorsatsen, då kan man bilda en separation där kanterna med en ändpunkt i $A$ tillhör $G_{1}$ , kanterna med en ändpunkt i $B$ tillhör $G_{2 }$ , och de återstående kanterna (med båda ändpunkterna i $S$ ) partitioneras godtyckligt.

Konstanten $2/3$$/2,1) }$ satsen för separatorsatsen är godtycklig och kan ersättas med vilket annat tal som helst i det ) utan att ändra formen på satsen: en partition i mer lika delmängder kan erhållas från en mindre jämn partition genom att upprepade gånger dela upp de större uppsättningarna i den ojämna partitionen och omgruppera de resulterande anslutna komponenterna.

Exempel

En plan avgränsare för en rutnätsgraf

Betrakta ett rutnätsdiagram med $r$ rader och $c$ kolumner; antalet $n$ av hörn är lika med $rc$ . Till exempel, i illustrationen, $r=5$ , $c=8$ och $n=rc=40$ . Om $r$ är udda, finns det en enda central rad, och annars finns det två rader lika nära mitten; på liknande sätt, om $c$ är udda, finns det en enda central kolumn, och annars finns det två kolumner lika nära mitten. Genom att välja $S$ som någon av dessa centrala rader eller kolumner, och ta bort $S$ från grafen, delas grafen upp i två mindre sammankopplade subgrafer $A$ och $B$ , som var och en har högst $n/2$ hörn. Om $r\leq c$ (som i illustrationen), då val av en central kolumn kommer att ge en separator $S$ med $r\leq {\sqrt {n} }$ hörn, och på liknande sätt om $c\leq r$ då val av en central rad ger en avgränsare med högst ${\sqrt {n}}$ hörn. Således har varje rutnätsdiagram en separator $S$ av storleken som högst ${\displaystyle {\sqrt {n}}} ,$ vars borttagning delar upp den i två anslutna komponenter, var och en av storleken högst $n/2$ .

Planarseparatorsatsen säger att en liknande partition kan konstrueras i vilken plan graf som helst. Fallet med godtyckliga plana grafer skiljer sig från fallet med rutnätsgrafer genom att separatorn har storlek $O({\sqrt {n}})$ men kan vara större än ${\sqrt { n}}$ , gränsen för storleken på de två delmängderna $A$ och $B$ (i de vanligaste versionerna av satsen) är snarare $2n/3$ än $n/2$ , och de två delmängderna $A$ och $B$ behöver inte själva bilda sammankopplade subgrafer.

Konstruktioner

Bredd-första lager

Lipton & Tarjan (1979) utökar den givna plana grafen med ytterligare kanter, om nödvändigt, så att den blir maximal plan (varje yta i en plan inbäddning är en triangel). De utför sedan en sökning med bredd först , rotad på en godtycklig vertex $v$ , och delar upp hörnen i nivåer efter deras avstånd från $v$ . Om $l_{1}$ är mediannivån (nivån så att antalet hörn på högre och lägre nivåer är båda högst ${\displaystyle n/2} )$ så måste det finnas nivåer $l_{0}$ och $l_{2}$ som är $O({\sqrt {n}})$ steg över och under $l_{ 1}$ respektive och som innehåller $O({\sqrt {n}})$ hörn, för annars skulle det finnas fler än $n$ hörn i nivåerna nära ${ \displaystyle l_{1}}$ . De visar att det måste finnas en separator $S$ bildad av föreningen av $l_{0}$ och $l_{2}$ , ändpunkterna för en kant $e$ av $G$ som inte hör till bredd-första sökträdet och som ligger mellan de två nivåerna, och hörnen på de två bredd-första sökträdets vägar från ändpunkterna av e {\displaystyle $}$ tillbaka upp till nivå $l_{0}$ . Storleken på separatorn $S$ konstruerad på detta sätt är som mest ${\sqrt {8n}}\approx 2.83{\sqrt {n}}$ . Avskiljarens hörn och de två disjunkta subgraferna kan hittas i linjär tid .

Detta bevis för separatorsatsen gäller också för viktade plana grafer, där varje vertex har en icke-negativ kostnad. Grafen kan delas upp i tre uppsättningar $A$ , $S$ och $B$ så att $A$ och $B$ vardera har högst $2/3$ av den totala kostnaden och $S$ har $O({\sqrt {n}})$ hörn, utan kanter från $A$ och $B$ . Genom att analysera en liknande separatorkonstruktion mer noggrant Djidjev (1982) att gränsen på storleken på $S$ kan reduceras till ${\sqrt {6n}}\approx 2,45{ \sqrt {n}}$ .

Holzer et al. (2009) föreslår en förenklad version av detta tillvägagångssätt: de utökar grafen till att vara maximal plan och konstruerar ett breddförsta sökträd som tidigare. Sedan, för varje kant $e$ som inte är en del av trädet, bildar de en cykel genom att kombinera $e$ med trädvägen som förbinder dess ändpunkter. De använder sedan som en separator hörn av en av dessa cykler. Även om detta tillvägagångssätt inte kan garanteras att hitta en liten separator för plana grafer med hög diameter, indikerar deras experiment att den överträffar Lipton-Tarjan och Djidjev bredd-första skiktningsmetoder på många typer av plana grafer.

Enkla cykelseparatorer

För en graf som redan är maximal plan är det möjligt att visa en starkare konstruktion av en enkel cykelseparator , en cykel av liten längd så att insidan och utsidan av cykeln (i den unika plana inbäddningen av grafen) var och en har vid mest $2n/3$ hörn. Miller (1986) bevisar detta (med en separatorstorlek på ${\sqrt {8n}}$ ) genom att använda Lipton–Tarjan-tekniken för en modifierad version av breddförsta sökning där söknivåerna är enkla cykler.

Alon, Seymour & Thomas (1994) bevisar existensen av enkla cykelseparatorer mer direkt: de låter $C$ vara en cykel av högst ${\sqrt {8n}}$ hörn, med som mest $2n/3$ hörn utanför ${\displaystyle C} ,$ som bildar en så jämn partition av insidan och utsidan som möjligt, och de visar att dessa antaganden tvingar $C$ att vara en separator . För annars måste avstånden inom $C$ vara lika med avstånden i skivan som omges av $C$ (en kortare väg genom skivans inre skulle utgöra en del av gränsen för en bättre cykel). Dessutom måste ${\displaystyle C} ha längden exakt$${\displaystyle {\sqrt {8n}}} ,$ eftersom den annars skulle kunna förbättras genom att ersätta en av dess kanter med de andra två sidorna av en triangel. Om hörn i $C$ är numrerade (i medurs ordning) från $1$ till ${\sqrt {8n}}$ och vertex $i$ matchas upp med vertex ${\displaystyle {\sqrt {8n}}-i+1} ,$ då kan dessa matchade par kopplas samman med vertex-disjunkta banor inom skivan, genom en form av Mengers sats för plana grafer. Den totala längden på dessa vägar skulle dock nödvändigtvis överstiga ${\displaystyle n} ,$ en motsägelse. Med lite extra arbete visar de med en liknande metod att det finns en enkel cykelseparator med storleken högst ${\sqrt {9n/2}}\approx 2.12{\sqrt {n}}$ .

Djidjev & Venkatesan (1997) förbättrade ytterligare konstantfaktorn i den enkla cykelseparatorsatsen till $1,97{\sqrt {n}}$ . Deras metod kan också hitta enkla cykelseparatorer för grafer med icke-negativa vertexvikter, med separatorstorlek som högst ${\displaystyle 2{\sqrt {n}}} ,$ och kan generera separatorer med mindre storlek på bekostnad av en mer ojämn uppdelning av grafen. I dubbelkopplade plana grafer som inte är maximala, finns det enkla cykelseparatorer med storlek proportionell mot den euklidiska normen för vektorn av ytlängder som kan hittas i nästan linjär tid.

Cirkelavskiljare

Enligt Koebe–Andreev–Thurstons cirkelpackningssats kan vilken plan graf som helst representeras av en packning av cirkulära skivor i planet med disjunkta inre, så att två hörn i grafen är intill varandra om och endast om motsvarande par skivor tangerar varandra. Som Miller et al. (1997) visar att det för en sådan packning finns en cirkel som har högst $3n/4$ skivor som rör vid eller inuti den, högst $3n/4$ skivor som rör vid varandra eller utanför den, och som korsar $O({\sqrt {n}})$ diskar.

För att bevisa detta har Miller et al. använd stereografisk projektion för att kartlägga packningen på ytan av en enhetssfär i tre dimensioner. Genom att välja projektionen noggrant kan sfärens centrum göras till en mittpunkt av skivan centreras på dess yta, så att vilket plan som helst genom sfärens mitt delar upp den i två halvrum som var och en innehåller eller korsar högst $3n/4$ av diskarna. Om ett plan genom mitten väljs likformigt slumpmässigt, kommer en skiva att korsas med sannolikhet proportionell mot dess radie. Därför är det förväntade antalet skivor som korsas proportionellt mot summan av skivornas radier. Summan av radiernas kvadrater är dock proportionell mot skivornas totala yta, vilket är som mest enhetssfärens totala yta, en konstant. Ett argument som involverar Jensens olikhet visar att när summan av kvadrater av $n$ icke-negativa reella tal begränsas av en konstant, är summan av själva talen $O({\sqrt {n}})$ . Därför är det förväntade antalet skivor som korsas av ett slumpmässigt plan $O({\sqrt {n}})$ och det finns ett plan som korsar högst så många skivor. Detta plan skär sfären i en storcirkel , som projicerar tillbaka ner till en cirkel i planet med önskade egenskaper. O ${\displaystyle O({\sqrt {n}})}-$ skivorna som korsas av denna cirkel motsvarar hörnen på en plan grafseparator som skiljer de hörn vars skivor är inuti cirkeln från de hörn vars skivor är cirkeln, med högst $3n/4$ hörn i var och en av dessa två delmängder.

Denna metod leder till en randomiserad algoritm som hittar en sådan separator i linjär tid och en mindre praktisk deterministisk algoritm med samma linjära tidsgräns. Genom att noggrant analysera denna algoritm med hjälp av kända gränser för packningstätheten för cirkelpackningar , kan det visas att man som mest hittar separatorer av storlek

$${\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}} }+o(1)\right){\sqrt {n}}\approx 1,84{\sqrt {n}}.$$

Även om denna förbättrade separatorstorleksgräns kommer på bekostnad av en mer ojämn partition av grafen, hävdar Spielman & Teng (1996) att den ger en förbättrad konstant faktor i tidsgränserna för kapslad dissektion jämfört med separatorerna i Alon, Seymour & Thomas (1990) . Storleken på separatorerna som den producerar kan förbättras ytterligare, i praktiken, genom att använda en ojämn fördelning för de slumpmässiga skärplanen.

Den stereografiska projektionen i Miller et al. argument kan undvikas genom att betrakta den minsta cirkeln som innehåller en konstant bråkdel av skivornas mittpunkter och sedan utöka den med en konstant plockad likformigt i området [ $\displaystyle [1,2]}$ . Liksom i Miller et al., bildar skivorna som skär den expanderade cirkeln en giltig separator, och i förväntan är separatorn av rätt storlek. De resulterande konstanterna är något sämre.

Spektral uppdelning

Spektralklustringsmetoder , där hörn av en graf grupperas efter koordinaterna för egenvektorerna för matriser härledda från grafen, har länge använts som en heuristik för grafpartitioneringsproblem för icke-planära grafer. Som Spielman & Teng (2007) visar kan spektralklustring också användas för att härleda ett alternativt bevis för en försvagad form av planseparatorsatsen som gäller för plana grafer med begränsad grad. I deras metod sorteras hörnen för en given plan graf efter de andra koordinaterna för egenvektorerna för grafens Laplacian-matris , och denna sorterade ordning är uppdelad vid den punkt som minimerar förhållandet mellan antalet kanter som skärs av partitionen till antalet hörn på den mindre sidan av partitionen. Som de visar har varje plan graf med begränsad grad en partition av denna typ där förhållandet är $O(1/{\sqrt {n}})$ . Även om denna partition kanske inte är balanserad, kommer en upprepning av partitionen inom den större av de två sidorna och föreningen av snitten som bildas vid varje upprepning så småningom att leda till en balanserad partition med O ( n ) {\ $\sqrt { n}})}$ kanter. Ändpunkterna för dessa kanter bildar en separator med storleken $O({\sqrt {n}})$ .

Kantavskiljare

En variant av planseparatorsatsen involverar kantseparatorer , små uppsättningar av kanter som bildar ett snitt mellan två delmängder $A$ och $B$ i grafens hörn. De två uppsättningarna $A$ och $B$ måste vardera ha storleken högst en konstant bråkdel av antalet $n$ av grafens hörn (vanligtvis har båda uppsättningarna storlek högst $2n/3$ ), och varje vertex i grafen tillhör exakt en av $A$ och $B$ . Separatorn består av kanterna som har en ändpunkt i $A$ och en ändpunkt i $B$ . Gränser för storleken på en kantavskiljare involverar graden av hörn såväl som antalet hörn i grafen: de plana graferna där en vertex har graden ${\displaystyle n-1} ,$ inklusive hjulgraferna och stjärndiagram , har ingen kantavskiljare med ett sublinjärt antal kanter, eftersom varje kantavskiljare måste inkludera alla kanter som förbinder höggradspunkten med hörn på andra sidan av snittet. Varje plan graf med maximal grad $\Delta$ har dock en kantavskiljare med storleken $O({\sqrt {\Delta n}})$ .

En enkel cykelseparator i den dubbla grafen i en plan graf bildar en kantseparator i den ursprungliga grafen. Genom att tillämpa den enkla cykelseparatorsatsen från Gazit & Miller (1990) på den dubbla grafen för en given plan graf förstärks $O({\sqrt {\Delta n}})$ bunden för storleken på en kantseparator genom att visa att varje plan graf har en kantseparator vars storlek är proportionell mot den euklidiska normen för dess vektor av vertexgrader.

Papadimitriou & Sideri (1996) beskriver en polynomisk tidsalgoritm för att hitta den minsta kantseparatorn som delar upp en graf $G$ i två subgrafer av samma storlek, när $G$ är en inducerad subgraf till en rutnätsgraf med inga hål eller med ett konstant antal hål. Men de gissar att problemet är NP-komplett för godtyckliga plana grafer, och de visar att problemets komplexitet är densamma för rutnätsgrafer med godtyckligt många hål som det är för godtyckliga plana grafer.

Nedre gränser

En polyeder bildad genom att ersätta var och en av ytorna på en ikosaeder med ett nät av 100 trianglar, ett exempel på den nedre konstruktionen av Djidjev (1982)

I ett ${\sqrt {n}}\times {\sqrt {n}}$ rutnätsdiagram, en uppsättning $S$ av $s<{\sqrt {n }}$ punkter kan omsluta en delmängd av högst $s(s-1)/2$ rutnätspunkter, där det maximala uppnås genom att arrangera $S$ i en diagonal linje nära ett hörn av rutnätet. Därför, för att bilda en separator som separerar minst $n/3$ av punkterna från det återstående rutnätet, måste $s$ vara minst ${\ displaystyle {\sqrt {2n/3}}\approx 0,82{\sqrt {n}}}$ .

Det finns $n$ -vertex plana grafer (för godtyckligt stora värden på $n$ ) så att för varje separator $S$ som delar upp den återstående grafen i subgrafer på högst $2n/3$ hörn, $S$ har minst ${\sqrt {4\pi n/{\sqrt {27}}}}\approx 1,56{\sqrt {n}}$ . Konstruktionen innebär att man approximerar en sfär med en konvex polyeder , ersätter var och en av polyederns ytor med ett triangulärt nät, och applicerar isoperimetriska satser för sfärens yta.

Separatorhierarkier

Separatorer kan kombineras till en separatorhierarki av en plan graf, en rekursiv uppdelning till mindre grafer. En separatorhierarki kan representeras av ett binärt träd där rotnoden representerar själva grafen och rotens två barn är rötterna till rekursivt konstruerade separatorhierarkier för de inducerade subgraferna som bildas av de två delmängderna $A$ och $B$ av en separator.

En separatorhierarki av denna typ utgör grunden för en trädnedbrytning av den givna grafen, där uppsättningen av hörn associerade med varje trädnod är föreningen av separatorerna på vägen från den noden till trädets rot. Eftersom storleken på graferna går ner med en konstant faktor på varje nivå i trädet, sjunker även de övre gränserna för storlekarna på separatorerna med en konstant faktor på varje nivå, så storleken på separatorerna på dessa banor läggs till en geometrisk serie till $O({\sqrt {n}})$ . Det vill säga, en separator som bildas på detta sätt har bredd ${\displaystyle O({\sqrt {n}})} ,$ och kan användas för att visa att varje plan graf har trädbredd $O ({\sqrt {n}})$ .

${ \displaystyle O(n\log n)}$ och en av de inducerade subgraferna associerade med varje nod i det binära trädet, skulle ta totalt O tid. Det är dock möjligt att konstruera en hel separatorhierarki i linjär tid, genom att använda Lipton–Tarjans bredd-första skiktningsmetod och genom att använda lämpliga datastrukturer för att utföra varje partitionssteg i sublinjär tid.

Om man bildar en relaterad typ av hierarki baserad på separatorer istället för separatorer, där de två barnen i rotnoden är rötter till rekursivt konstruerade hierarkier för de två subgraferna $G_{1}$ och $G_{2}$ av en separation av den givna grafen, då bildar den övergripande strukturen en grennedbrytning istället för en trädupplösning. Bredden av varje separation i denna sönderdelning är, återigen, begränsad av summan av storleken på separatorerna på en väg från valfri nod till roten av hierarkin, så varje grennedbrytning som bildas på detta sätt har bredd $O({\sqrt {n}})$ och alla plana grafer har grenbredd $O({\sqrt {n}})$ . Även om många andra relaterade grafpartitioneringsproblem är NP-kompletta , även för plana grafer, är det möjligt att hitta en minimibredds grenuppdelning av en plan graf i polynomtid.

Genom att tillämpa metoder från Alon, Seymour & Thomas (1994) mer direkt i konstruktionen av grennedbrytningar, visar Fomin & Thilikos (2006a) att varje plan graf har en grenbredd på högst $2,12{\sqrt {n}}$ , med samma konstant som den i den enkla cykelseparatorsatsen av Alon et al. Eftersom trädbredden för en graf som mest är $3/2$ dess grenbredd, visar detta också att plana grafer har en trädbredd på högst $\displaystyle 3,18{\sqrt {n}}$ .

Andra klasser av grafer

Vissa glesa grafer har inte separatorer av sublinjär storlek: i en expandergraf lämnar radering upp till en konstant bråkdel av hörnen fortfarande bara en ansluten komponent.

Möjligen är den tidigaste kända separatorsatsen ett resultat av Jordan (1869) att vilket träd som helst kan delas in i underträd med högst $n/2$ hörn vardera genom att ta bort en enda vertex. Speciellt den vertex som minimerar den maximala komponentstorleken har denna egenskap, för om den inte gjorde det skulle dess granne i det unika stora underträdet bilda en ännu bättre partition. Genom att tillämpa samma teknik på en träduppdelning av en godtycklig graf, är det möjligt att visa att vilken graf som helst har en separator av storlek som högst är lika med dess trädbredd .

Om en graf $G$ inte är plan, utan kan bäddas in på en yta av släktet ${\displaystyle g} ,$ så har den en separator med $O({\sqrt {gn }})$ hörn. Gilbert, Hutchinson & Tarjan (1984) bevisar detta genom att använda ett liknande tillvägagångssätt som Lipton & Tarjan (1979) . De grupperar grafens hörn i bredd-första nivåer och hittar två nivåer vars borttagning lämnar högst en stor komponent bestående av ett litet antal nivåer. Denna återstående komponent kan göras plan genom att ta bort ett antal bredd-första banor proportionellt mot släktet, varefter Lipton-Tarjan-metoden kan tillämpas på den återstående plana grafen. Resultatet följer av en noggrann avvägning av storleken på de borttagna två nivåerna mot antalet nivåer mellan dem. Om grafinbäddningen ges som en del av inmatningen, kan dess separator hittas i linjär tid . Grafer av släktet $g$ har också kantavskiljare med storleken $O({\sqrt {g\Delta n}})$ .

Grafer av avgränsat släkte bildar ett exempel på en familj av grafer som stängs under driften av att ta minderåriga , och separatorsatser gäller också för godtyckliga mollslutna graffamiljer. I synnerhet, om en graffamilj har en förbjuden moll med $h$ hörn, så har den en separator med $O(h{\sqrt {n}})$ hörn, och sådant en separator kan hittas i tiden $O(n^{1+\varepsilon })$ för alla $\varepsilon >0$ .

En skärningsgraf av skivor, med högst $k=5$ skivor som täcker vilken punkt som helst i planet

Cirkelseparatormetoden enligt Miller et al. (1997) generaliserar till skärningsgraferna för alla system av $d$ -dimensionella bollar med egenskapen att varje punkt i rymden täcks av högst något konstant antal $k$ av bollar, till ${\ displaystyle k}$ - närmaste granne-grafer i $d$ -dimensioner, och till graferna som härrör från finita elementmaskor . Sfärseparatorerna som är konstruerade på detta sätt delar upp ingångsgrafen i subgrafer med högst $n(d+1)/(d+2)$ hörn. Storleken på separatorerna för $k$ -ply ball intersection graphs och för $k$ -närmaste granne-grafer är $O(k ^{1/d}n^{1-1/d})$ .

Om en ärftlig familj av grafer har en separatorsats med separatorer av storleken $n^{c}$ , för vissa $c<1$ , så har den nödvändigtvis polynomexpansion , ett polynom bundet på tätheten av dess grunda minderåriga . Omvänt har grafer med polynomexpansion sublinjära separatorsatser.

Ansökningar

Dela och erövra algoritmer

Separatornedbrytningar kan vara till nytta för att utforma effektiva dividera och erövra algoritmer för att lösa problem på plana grafer. Som ett exempel är ett problem som kan lösas på detta sätt att hitta den kortaste cykeln i en vägd plan digraf. Detta kan lösas genom följande steg:

• Dela upp den givna grafen $G$ i tre delmängder $S$ , $A$ , $B$ enligt planar separatorsatsen
• Sök rekursivt efter de kortaste cyklerna i $A$ och $B$
• Använd Dijkstras algoritm för att hitta, för varje vertex $s$ i $S$ , den kortaste cykeln genom $s$ i $G$ .
• Returnera den kortaste av cyklerna som hittats i stegen ovan.

Tiden för de två rekursiva anropen till $A$ och $B$ i denna algoritm domineras av tiden för att utföra $O({\sqrt {n}})$ anropar Dijkstras algoritm, så denna algoritm hittar den kortaste cykeln i $O(n^{3/2}\log n)$ tid.

En snabbare algoritm för samma kortaste cykelproblem, som körs i tiden ${\displaystyle O(n\log ^{3}n)} ,$ gavs av Wulff-Nilsen (2009) . Hans algoritm använder samma separatorbaserade divide and conquer-struktur, men använder enkla cykelseparatorer snarare än godtyckliga separatorer, så att hörnen på $S$ tillhör en enda sida av graferna inuti och utanför cykelseparatorn. Han ersätter sedan $O({\sqrt {n}})$ separata anrop till Dijkstras algoritm med mer sofistikerade algoritmer för att hitta de kortaste vägarna från alla hörn på en enda sida av en plan graf och för att kombinera avstånd från de två subgraferna. För viktade men oriktade plana grafer är den kortaste cykeln ekvivalent med den minsta snittet i den dubbla grafen och kan hittas i $O(n\log \log n)$ tid, och den kortaste cykeln i en oviktad oriktad plan graf (dess omkrets ) kan hittas i tiden $O(n)$ . (Den snabbare algoritmen för oviktade grafer är dock inte baserad på separatorsatsen.)

Frederickson föreslog en annan snabbare algoritm för enskild källas kortaste vägar genom att implementera separatorsats i plana grafer. Detta är en förbättring av Dijkstras algoritm med iterativ sökning på en noggrant utvald delmängd av hörnen. Denna version tar $O(n{\sqrt {\log n}})$ tid i en $n$ -vertexgraf. Separatorer används för att hitta en uppdelning av en graf, det vill säga en partition av kantuppsättningen i två eller flera delmängder, kallade regioner. En nod sägs vara innesluten i en region om någon kant av regionen faller in mot noden. En nod som finns i mer än en region kallas en gränsnod för de regioner som innehåller den. Metoden använder begreppet en $r$ -division av en $n$ -nodgraf som är en grafindelning i $O(n/r)$ regioner, var och en innehåller $O(r)$ -noder inklusive $O({\sqrt {r}})$ gränsnoder. Frederickson visade att en $r$ -division kan hittas i $O(n\log n)$ tid genom rekursiv tillämpning av separatorsatsen.

Skissen av hans algoritm för att lösa problemet är som följer.

1. Förbearbetningsfas: Dela upp grafen i noggrant utvalda delmängder av hörn och bestäm de kortaste vägarna mellan alla par av hörn i dessa delmängder, där mellanliggande hörn på denna väg inte finns i delmängden. Denna fas kräver att en plan graf $G_{0}$ omvandlas till $G$ utan att någon vertex har en grad som är större än tre. Från en följd av Eulers formel kommer antalet hörn i den resulterande grafen att vara ${\displaystyle n\leq 6n_{0}-12} ,$ där $n_{0}$ är antalet hörn i $G_{0}$ . Denna fas säkerställer också följande egenskaper för en lämplig $r$ -division. En lämplig $r$ -division av en plan graf är en $r$ -division så att,
   • varje gränspunkt finns i högst tre regioner, och
   • varje region som inte är ansluten består av anslutna komponenter, som alla delar gränspunkt med exakt samma uppsättning av antingen en eller två anslutna regioner.
2. Sökfas:
   • Main Thrust: Hitta kortaste avstånden från källan till varje vertex i delmängden. När en vertex $v$ i delmängden stängs, måste det preliminära avståndet $d(w)$ uppdateras för alla hörn $w$ i delmängden så att en sökväg finns från $v$ till $w$ .
   • Mop-up: Bestäm kortaste avstånd till varje återstående vertex.

Henzinger et al. utökade Fredericksons $r$ -divisionsteknik för algoritmen för den enkla källans kortaste väg i plana grafer för icke-negativa kantlängder och föreslog en linjär tidsalgoritm . Deras metod generaliserar Fredericksons föreställning om grafdivisioner så att nu en $(r,s)$ -division av en $n$ -nodgraf är en division i $O(n/r)$ regioner, som var och en innehåller $r^{O(1)}$ noder, var och en har högst $s$ gränsnoder. Om en $(r,s)$ -division upprepade gånger delas in i mindre områden, kallas det en rekursiv division. Denna algoritm använder ungefär $\log ^{*}n$ nivåer av divisioner, där $\log ^{*}$ anger den itererade logaritmfunktionen . Den rekursiva divisionen representeras av ett rotat träd vars löv är märkta med en distinkt kant på $G$ . Trädets rot representerar regionen som består av alla $G$ , barnen i roten representerar underregionerna som regionen är indelad i och så vidare. Varje blad (atomområde) representerar en region som innehåller exakt en kant.

Kapslad dissektion är en separatorbaserad dividera och erövra-variation av Gauss-eliminering för att lösa glesa symmetriska system av linjära ekvationer med en plan grafstruktur, till exempel de som härrör från finita elementmetoden . Det går ut på att hitta en separator för grafen som beskriver ekvationssystemet, rekursivt eliminera variablerna i de två delproblemen som separeras från varandra av separatorn och sedan eliminera variablerna i separatorn. Fyllningen av denna metod (antalet koefficienter som inte är noll för den resulterande Cholesky-nedbrytningen av matrisen) är ${\displaystyle O(n\log n)} ,$ vilket gör att denna metod kan vara konkurrenskraftig med iterativ metoder för samma problem.

Klein, Mozes och Weimann gav en $O(n\log ^{2}n)$ -tid, linjär-rymdsalgoritm för att hitta de kortaste vägavstånden från en källpunkt ${\ displaystyle s}$ till alla andra hörn för en riktad plan graf med positiva och negativa båglängder som inte innehåller några negativa cykler. Deras algoritm använder plana grafseparatorer för att hitta en Jordan-kurva $C$ som passerar genom $O({\sqrt {n}})$ noder (och inga bågar) så att mellan $n/3$ och $2n/3$ noder omges av $C$ . Noder genom vilka $C$ passerar är gränsnoder . Den ursprungliga grafen $G$ är uppdelad i två subgrafer $G_{0}$ och $G_{1}$ genom att skära den plana inbäddningen längs $C$ och duplicera gränsen knutpunkter. Gränsnoderna i varje graf $G_{i}$ ligger på gränsen för en enda yta $F_{i}$ .

Översikten över deras tillvägagångssätt ges nedan.

• Rekursivt anrop: Det första steget beräknar rekursivt avstånden från $r$ inom varje graf $G_{i}$ .
• Interna gränsavstånd: För varje graf beräknar ${\displaystyle G_{i}} alla avstånd$$G_{i}$ mellan gränsnoder. Detta tar $O(n\log n)$ tid.
• Enkällas gränsavstånd mellan delar: En kortaste väg i $G$ passerar fram och tillbaka mellan $G_{0}$ och $G_{1}$ för att beräkna avstånden i $G$ från $r$ till alla gränsnoder. Alternerande iterationer använder all-boundary-distanserna i $G_{0}$ och $G_{1}$ . Antalet iterationer är $O({\sqrt {n}})$ , och den totala tiden för detta steg är $O(n\alpha (n) ))$ där $\alpha (n)$ är den omvända Ackermann-funktionen .
• Enkällas avstånd mellan delar: Avstånden som beräknats i de föregående stegen används tillsammans med en Dijkstra-beräkning inom en modifierad version av varje Gi för att _beräkna avstånden i $G$ från $r$ till alla noder. Detta steg tar $O(n\log n)$ tid.
• Omrota avstånd med en källa: Avstånden från $r$ i $G$ omvandlas till icke-negativa längder, och återigen används Dijkstras algoritm för att beräkna avstånd från $s$ . Detta steg kräver $O(n\log n)$ tid.

En viktig del av denna algoritm är användningen av prisfunktioner och reducerade längder. För en riktad graf $G$ med båglängder $\ell (uv)$ , är en prisfunktion en funktion $\varphi$ från noderna för $G$ till de reella talen . För en båge $uv$ är den reducerade längden med avseende på $\varphi$$\ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)$ . En genomförbar prisfunktion är en prisfunktion som inducerar icke-negativa reducerade längder på alla bågar av $G$ . Det är användbart för att omvandla ett problem med kortaste vägen som involverar positiva och negativa längder till ett som endast involverar icke-negativa längder, som sedan kan lösas med Dijkstras algoritm.

Det separatorbaserade dela och erövra paradigmet har också använts för att designa datastrukturer för dynamiska grafalgoritmer och punktplacering , algoritmer för polygontriangulering , kortaste vägar och konstruktion av närmaste granngrafer , och approximationsalgoritmer för den maximala oberoende uppsättningen av en plan. Graf.

Exakt lösning av NP-hårda optimeringsproblem

Genom att använda dynamisk programmering på en trädsönderdelning eller grennedbrytning av en plan graf kan många NP-hårda optimeringsproblem lösas i exponentiell tid i ${\sqrt {n}}$ eller ${\sqrt {n}}\log n$ . Till exempel är gränser för denna form kända för att hitta maximala oberoende uppsättningar , Steiner-träd och Hamiltonska cykler , och för att lösa problemet med resande försäljare på plana grafer. Liknande metoder som involverar separatorsatser för geometriska grafer kan användas för att lösa problem med euklidiska resandeförsäljare och Steinerträdkonstruktionsproblem inom tidsgränser av samma form.

För parametriserade problem som tillåter en kärnbildning som bevarar planaritet och reducerar ingångsgrafen till en kärna med storlek linjär i indataparametern, kan detta tillvägagångssätt användas för att designa algoritmer med fasta parametrar vars körtid beror polynomiellt på storleken på mata in grafen och exponentiellt på ${\sqrt {k}}$ , där $k$ är parametern för algoritmen. Till exempel är tidsgränser för denna form kända för att hitta vertextäcken och dominerande uppsättningar av storleken $k$ .

Approximationsalgoritmer

Lipton & Tarjan (1980) observerade att separatorsatsen kan användas för att erhålla polynomtidsapproximationsscheman för NP-hårda optimeringsproblem på plana grafer, såsom att hitta den maximala oberoende mängden . Närmare bestämt, genom att trunkera en separatorhierarki på en lämplig nivå, kan man hitta en separator av storleken $O(n/{\sqrt {\log n}})$ vars partitioner tas bort grafen till subgrafer av storlek som mest $c\log n$ , för varje konstant $c$ . Enligt fyrfärgssatsen finns det en oberoende uppsättning av storlek åtminstone ${\displaystyle n/4} ,$ så de borttagna noderna bildar en försumbar bråkdel av den maximala oberoende mängden, och de maximala oberoende uppsättningarna i de återstående subgraferna kan hittas oberoende i tid exponentiell i sin storlek. Genom att kombinera detta tillvägagångssätt med senare linjära tidsmetoder för separatorhierarkikonstruktion och med tabelluppslag för att dela beräkningen av oberoende uppsättningar mellan isomorfa subgrafer, kan det göras att konstruera oberoende uppsättningar av storlek inom en faktor $1-1/{\sqrt {\log n}}$ av optimal, i linjär tid. Men för approximationsförhållanden som är ännu närmare en än denna faktor, ger ett senare tillvägagångssätt av Baker (1994) (baserat på trädnedbrytning men inte på plana separatorer) bättre avvägningar mellan tid och approximationskvalitet.

Liknande separatorbaserade approximationsscheman har också använts för att approximera andra svåra problem såsom vertextäckning . Arora et al. (1998) använder separatorer på ett annat sätt för att approximera problemet med resande försäljare för den kortaste vägen på vägda plana grafer; deras algoritm använder dynamisk programmering för att hitta den kortaste turen som, på varje nivå i en separatorhierarki, korsar separatorn ett begränsat antal gånger, och de visar att när korsningsgränsen ökar, har de turer som är konstruerade på detta sätt längder som är ungefärliga Turné.

Grafkomprimering

Separatorer har använts som en del av datakomprimeringsalgoritmer för att representera plana grafer och andra separerbara grafer med ett litet antal bitar. Grundprincipen för dessa algoritmer är att välja ett tal $k$ och upprepade gånger dela upp den givna plana grafen med hjälp av separatorer i $O(n/k)$ subgrafer med högst storlek ${ \displaystyle k}$ , med $O(n/{\sqrt {k}})$ hörn i separatorerna. Med ett lämpligt val av $k$ (högst proportionell mot logaritmen av $n$ ) är antalet icke-isomorfa $k$ -vertex plana subgrafer betydligt mindre än antalet subgrafer i nedbrytningen, så att grafen kan komprimeras genom att konstruera en tabell över alla möjliga icke-isomorfa subgrafer och representera varje subgraf i separatoruppdelningen med dess index i tabellen. Återstoden av grafen, som bildas av separatorpunkten, kan representeras explicit eller genom att använda en rekursiv version av samma datastruktur. Med denna metod kan plana grafer och många fler begränsade familjer av grafer kodas med ett antal bitar som är informationsteoretiskt optimala: om det finns $P_{n}$$n$ -vertexgrafer i familjen av grafer som ska representeras, då kan en enskild graf i familjen representeras med endast $(1+o(1))\log _{2 }P_{n}$ bitar. Det är också möjligt att konstruera representationer av denna typ där man kan testa närhet mellan hörn, bestämma graden av en vertex och lista grannar till hörn i konstant tid per fråga, genom att utöka tabellen med subgrafer med ytterligare tabellinformation som representerar svaren till frågorna.

Universella grafer

En universell graf för en familj ${\mathcal {F}}$ av grafer är en graf som innehåller varje medlem av ${\mathcal {F}}$ som subgrafer. Separatorer kan användas för att visa att de $n$ -vertex plana graferna har universella grafer med $n$ hörn och $O(n^{3/2})$ kanter.

Konstruktionen innebär en förstärkt form av separatorsatsen där storleken på de tre delmängderna av hörn i separatorn inte beror på grafstrukturen: det finns ett tal c {\ $c} ,$ vars storlek högst är en konstant gånger ${\sqrt {n}}$ , så att hörnen för varje $n$ -vertex plan graf kan separeras i delmängder ${\displaystyle A} ,$ S $\displaystyle S}$ , och $B$ , utan kanter från $A$ till $B$ , med $|S|=c$ , och med $|A|=|B|=(nc)/2$ . Detta kan visas genom att använda den vanliga formen av separatorsatsen upprepade gånger för att partitionera grafen tills alla komponenter i partitionen kan ordnas i två delmängder med färre än $n/2$ hörn, och sedan rörliga hörn från dessa delmängder till separatorn efter behov tills den har den givna storleken.

När en separatorsats av denna typ visas kan den användas för att skapa en separatorhierarki för $n$ -vertex plana grafer som återigen inte beror på grafstrukturen: träduppdelningen som bildas från denna hierarki har bredd $O({\sqrt {n}})$ och kan användas för vilken plan graf som helst. Mängden av alla par av hörn i denna trädnedbrytning som båda tillhör en gemensam nod av trädupplösningen bildar en trivialt perfekt graf med $O(n^{3/2})$ hörn som innehåller varje $n$ -vertex plan graf som en subgraf. En liknande konstruktion visar att avgränsade graders plana grafer har universella grafer med $O(n\log n)$ kanter, där konstanten som döljs i O-notationen beror på gradgränsen. Alla universella grafer för plana grafer (eller till och med för träd med obegränsad grad) måste ha $\Omega (n\log n)$ kanter.

Esperet, Joret & Morin (2020) meddelade att ${\displaystyle O(n^{3/2})}-$ konstruktionen med separatorer kan förbättras, till $n^{1+o(1)}$ .

Se även

• Vertexavskiljare
• Geometrisk separator

Anteckningar

• Alber, Jochen; Fernau, Henning; Niedermeier, Rolf (2003), "Graph separators: A parameterized view", Journal of Computer and System Sciences , 67 (4): 808–832, doi : 10.1016/S0022-0000(03)00072-2
• Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "A separator theorem for nonplanar graphs", Journal of the American Mathematical Society , 3 (4): 801–808, doi : 10.1090/S0894-0347-1990-1065053-0
• Alon, Noga ; Seymour, Paul ; Thomas, Robin (1994), "Planar separators", SIAM Journal on Discrete Mathematics , 7 (2): 184–193, doi : 10.1137/S0895480191198768
•   Arora, Sanjeev ; Grigni, Michelangelo; Karger, David; Klein, Philip; Woloszyn, Andrzej (1998), "A polynom-time approximation scheme for weighted planar graph TSP", Proc. 9:e ACM-SIAM-symposiet om diskreta algoritmer (SODA '98) , s. 33–41, ISBN 9780898714104
• Babai, L .; Chung, FRK ; Erdős, P. ; Graham, RL ; Spencer, JH (1982), "Om grafer som innehåller alla glesa grafer", i Rosa, Alexander; Sabidussi, Gert ; Turgeon, Jean (red.), Teori och praktik av kombinatorik: en samling artiklar som hedrar Anton Kotzig med anledning av hans sextioårsdag ( PDF) , Annals of Discrete Mathematics, vol. 12, s. 21–26
•   Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 970677
•    Bar-Yehuda, R.; Even, S. (1982), "On approximating a vertex cover for planar graphs", Proc. 14:e ACM Symposium on Theory of Computing (STOC '82) : 303–309, doi : 10.1145/800070.802205 , ISBN 0-89791-070-2 , S2CID 2820550
• Bern, Marshall (1990), "Faster exact algorithms for Steiner trees in planar networks", Networks , 20 (1): 109–120, doi : 10.1002/net.3230200110
• Bhatt, Sandeep N.; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989), "Universal graphs for bounded-degree trees and planar graphs" (PDF) , SIAM Journal on Discrete Mathematics , 2 (2): 145, doi : 10.1137/0402014
• Blandford, Daniel K.; Blloch, Guy E.; Kash, Ian A. (2003), "Kompakta representationer av separerbara grafer", Proc. 14:e ACM-SIAM-symposiet om diskreta algoritmer (SODA '03) (PDF) , s. 679–688
•    Blloch, Guy E.; Farzan, Arash (2010), "Succinc representations of separable graphs", i Amir, Amihood; Parida, Laxmi (red.), Proc. 21st Symposium on Combinatorial Pattern Matching , Lecture Notes in Computer Science, vol. 6129, Springer-Verlag, s. 138–150, Bibcode : 2010LNCS.6129..138B , CiteSeerX 10.1.1.307.6710 , doi : 10.1007/978-3-6129..138B 3_642-9 I-3_509-2, 7-3_509-2, 7-3_509-2 , 7-3_509-2 13508 -8
• Chalermsook, Parinya; Fakcharoenphol, Jittat; Nanongkai, Danupon (2004), "En deterministisk näralinjär tidsalgoritm för att hitta minimisnitt i plana grafer", Proc. 15:e ACM–SIAM-symposiet om diskreta algoritmer (SODA'04) , s. 828–829
•   Chang, Hsien-Chih; Lu, Hsueh-I (2011), "Computing the girth of a planar graph in linear time", SIAM Journal on Computing , 42 (3): 1077–1094, arXiv : 1104.4892 , doi : 10.1137/110833C 9 , S7203C , 23083C 9
• Chiba, Norishige; Nishizeki, Takao ; Saito, Nobuji (1981), "Applications of the Lipton and Tarjan planar separator theorem" (PDF) , Journal of Information Processing , 4 (4): 203–207
•   Chung, Fan RK (1990), "Separatorsatser och deras tillämpningar", i Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (red.), Paths, Flows, and VLSI-Layout , Algorithms and Combinatorics, vol. 9, Springer-Verlag, s. 17–34 , ISBN 978-0-387-52685-0
• Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006), "Exact algorithms for the Hamiltonian cycle problem in planar graphs", Operations Research Letters , 34 (3): 269–274, doi : 10.1016/j.orl.2005.04.013
• Diks, K.; Djidjev, HN; Sykora, O.; Vrt'o, I. (1993), "Edge separators of planar and outerplanar graphs with applications", Journal of Algorithms , 14 (2): 258–279, doi : 10.1006/jagm.1993.1013
• Djidjev, HN (1982), "On the problem of partitioning planar graphs", SIAM Journal on Algebraic and Discrete Methods , 3 (2): 229–240, doi : 10.1137/0603022
•   Djidjev, Hristo N.; Venkatesan, Shankar M. (1997), "Reduced constants for simple cycle graph separation", Acta Informatica , 34 (3): 231–243, doi : 10.1007/s002360050082 , S2CID 8406777
• Donath, VI; Hoffman, AJ (1972), "Algorithms for partitioning of graphs and computer logic based on eigenvectors of anslutningsmatriser", IBM Techn. Avslöjande Bull. , 15 : 938–944 , som citeras av Spielman & Teng (2007)
•   Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L. ; Fomin, Fedor V. (2005), "Effektiva exakta algoritmer på plana grafer: utnyttjande av sfäriska grennedbrytningar", Proc. 13th European Symposium on Algorithms (ESA '05) , Lecture Notes in Computer Science, vol. 3669, Springer-Verlag, s. 95–106, doi : 10.1007/11561071_11 , ISBN 978-3-540-29118-3
•    Dvořák, Zdeněk; Norin, Sergey (2016), "Strongly sublinear separators and polynomial expansion", SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , doi : 10.1137 /15M1017/15M101, 3ID 5 , 47 5 , 47 5 , 29 95359
• Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F. ; Spencer, Thomas H. (1996), "Separator based sparsification. I. Planarity testing and minimum spaning trees", Journal of Computer and System Sciences , 52 (1): 3–27, doi : 10.1006/jcss.1996.0002
• Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F.; Spencer, Thomas H. (1998), "Separator-based sparsification. II. Edge and vertex connectivity", SIAM Journal on Computing , 28 : 341, doi : 10.1137/S0097539794269072
• Eppstein, David ; Miller, Gary L .; Teng, Shang-Hua (1995), "A deterministic linear time algorithm for geometric separators and its applications" , Fundamenta Informaticae , 22 (4): 309–331, doi : 10.3233/FI-1995-2241
• Erdős, Paul ; Graham, Ronald ; Szemerédi, Endre (1976), "On sparse graphs with dense long paths", Computers and Mathematics with Applications (PDF) , Oxford: Pergamon, s. 365–369
• Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Sparse universella grafer för planaritet , arXiv : 2010.05779
•   Fiedler, Miroslav (1973), "Algebraic connectivity of graphs", Czechoslovak Mathematical Journal , 23 (98): 298–305, doi : 10.21136 / CMJ.1973.101168 , hdl : 10338.701ml 6cz/ 101d .
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006a), "New upper bounds on the decomposability of planar graphs" (PDF) , Journal of Graph Theory , 51 (1): 53–81, doi : 10.1002/jgt.20121
•   Fomin, Fedor V.; Thilikos, Dimitrios M. (2006b), "Dominating sets in planar graphs: branch-width and exponential speed-up", SIAM Journal on Computing , 36 (2): 281, doi : 10.1137 / S009753970241962ID 3232C
•   Frederickson, Greg N. (1987), "Fast algorithms for shortest paths in planar graphs, with applications", SIAM Journal on Computing , 16 (6): 1004–1022, doi : 10.1137/0216064 , MR 0917037
•    Frieze, Alan ; Miller, Gary L .; Teng, Shang-Hua (1992), "Separatorbaserad parallell dividera och erövra i beräkningsgeometri", Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA '92) (PDF) , s. 420–429, doi : 10.1145/140901.141934 , ISBN 0-89791-483-X , S92CID 49 , S9147
•   Gazit, Hillel; Miller, Gary L. (1990), "Planar separators and the Euclidean norm", Proc. International Symposium on Algorithms (SIGAL'90) (PDF) , Lecture Notes in Computer Science, vol. 450, Springer-Verlag, s. 338–347, doi : 10.1007/3-540-52921-7_83 , ISBN 978-3-540-52921-7
•   George, J. Alan (1973), "Nested dissection of a regular finite element mesh", SIAM Journal on Numerical Analysis , 10 (2): 345–363, doi : 10.1137/0710032 , JSTOR 2156361
• Gilbert, John R.; Hutchinson, Joan P .; Tarjan, Robert E. (1984), "A separator theorem for graphs of bounded genus", Journal of Algorithms , 5 (3): 391–407, doi : 10.1016/0196-6774(84)90019-1 , hdl : 1813 /6346
•   Gilbert, John R.; Tarjan, Robert E. (1986), "The analysis of a nested dissection algorithm", Numerische Mathematik , 50 (4): 377–404, doi : 10.1007/BF01396660 , S2CID 122591105
• Goodrich, Michael T. (1995), "Planar separators and parallell polygon triangulation", Journal of Computer and System Sciences , 51 (3): 374–389, doi : 10.1006/jcss.1995.1076
•   Gremban, Keith D.; Miller, Gary L .; Teng, Shang-Hua (1997), "Moments of inertia and graph separators" (PDF) , Journal of Combinatorial Optimization , 1 (1): 79–104, doi : 10.1023/A:1009763020645 , S2CID 37829
• Har-Peled, Sariel (2011), A Simple Proof of the Existence of a Planar Separator , arXiv : 1105.0103 , Bibcode : 2011arXiv1105.0103H
• Han, Xin; Kao, Ming-Yang; Lu, Hsueh-I (2000), "A fast general methodology for information-theoreically optimal encodings of graphs", SIAM Journal on Computing , 30 (3): 838–846, arXiv : cs/0101021 , doi : 10.11357/S09199775/S0919977
•   Henzinger, Monika R. ; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997), "Faster shortest-path algorithms for planar graphs", Journal of Computer and System Sciences , 55 (1, del 1): 3–23, doi : 10.1006/jcss.1997.1493 , MR 1473046
•   Holzer, Martin; Schulz, Frank; Wagner, Dorothea ; Prasinos, Grigorios; Zaroliagis, Christos (2009), "Engineering planar separator algorithms" , Journal of Experimental Algorithmics , 14 : 1.5–1.31, doi : 10.1145/1498698.1571635 , S2CID 578288
• Jordan, Camille (1869), "Sur les assemblages des lignes" , Journal für die reine und angewandte Mathematik , 70 : 185–190 , som citeras av Miller et al. (1997)
•   Kawarabayashi, Ken-Ichi ; Reed, Bruce (2010), "A separator theorem in minor-closed classes", Proc. 51:a årliga IEEE Symposium on Foundations of Computer Science , doi : 10.1109/FOCS.2010.22 , S2CID 15860361
•    Klein, Philip N.; Mozes, Shay; Weimann, Oren (2010), "Kortaste vägar i riktade plana grafer med negativa längder: ett linjärt mellanrum $O(n\log ^{2}n)$ -tidsalgoritm", ACM Transactions on Algoritms , 6 (2): Art. 30, 18, doi : 10.1145/1721837.1721846 , MR 2675697 , S2CID 3095131
•    Klein, Philip; Rao, Satish; Rauch, Monika; Subramanian, Sairam (1994), "Faster shortest-path algorithms for planar graphs", Proc. 26th ACM Symposium on Theory of Computing (STOC '94) , s. 27–37, doi : 10.1145/195058.195092 , ISBN 0-89791-663-8 , S2CID 185739
•   Łącki, Jakub; Sankowski, Piotr (2011), "Min-snitt och kortaste cykler i plana grafer i $O(n\log \log n)$ tid", Proc. 19th Annual European Symposium on Algorithms , Lecture Notes in Computer Science, vol. 6942, Springer-Verlag, s. 155–166, arXiv : 1104.4890 , doi : 10.1007/978-3-642-23719-5_14 , ISBN 978-3-642-23725CID 1,5007 / 978-3-642-23719-5_14  
•   Lipton, Richard J .; Rose, Donald J.; Tarjan, Robert E. (1979), "Generalized nested dissection", SIAM Journal on Numerical Analysis , 16 (2): 346–358, doi : 10.1137/0716027 , JSTOR 2156840
• Lipton, Richard J .; Tarjan, Robert E. (1979), "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics , 36 (2): 177–189, doi : 10.1137/0136016
•   Lipton, Richard J .; Tarjan, Robert E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing , 9 (3): 615–627, doi : 10.1137/0209046 , S2CID 12961628
• Miller, Gary L. (1986), "Finding small simple cycle separators for 2-connected planar graphs" (PDF) , Journal of Computer and System Sciences , 32 (3): 265–279, doi : 10.1016/0022-0000( 86)90030-9
•   Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separators for sphere-packings and nearest neighbor graphs", Journal of the ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , S2CID 17331739
•   Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1998), "Geometric separators for finite-element meshes", SIAM Journal on Scientific Computing , 19 (2): 364–386, CiteSeerX 10.1.1.307.2357 , doi : 10.1137/S10.1136/S1013428
• Pach, János ; Agarwal, Pankaj K. (1995), "Lipton–Tarjan Separator Theorem", Combinatorial Geometry , John Wiley & Sons, s. 99–102
•   Papadimitriou, CH ; Sideri, M. (1996), "The bisection width of grid graphs", Theory of Computing Systems , 29 (2): 97–110, doi : 10.1007/BF01305310 , S2CID 15617963
•   Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc. 5:e ACM-SIAM-symposiet om diskreta algoritmer (SODA '94) , s. 462–470, ISBN 9780898713299
•   Reed, Bruce ; Wood, David R. (2009), "A linear-time algorithm to find a separator in a graph exclusive a minor", ACM Transactions on Algorithms , 5 (4): 1–16, doi : 10.1145/1597036.1597043 , S2CID 760001 76
•   Seymour, Paul D .; Thomas, Robin (1994), "Call routing and the ratcatcher", Combinatorica , 14 (2): 217–241, doi : 10.1007/BF01215352 , S2CID 7508434
•   Smith, Warren D.; Wormald, Nicholas C. (1998), "Geometric separator theorems & applications", 39th Annual Symposium on Foundations of Computer Science (FOCS '98), 8-11 november 1998, Palo Alto, Kalifornien, USA, IEEE Computer Society, pp. . 232–243, doi : 10.1109/SFCS.1998.743449 , S2CID 17962961
•    Spielman, Daniel A. ; Teng, Shang-Hua (1996), "Diskpackings and planar separators", Proc. 12th ACM Symposium on Computational Geometry (SCG '96) (PDF) , s. 349–358, doi : 10.1145/237218.237404 , ISBN 0-89791-804-5 , S23701 599
• Spielman, Daniel A. ; Teng, Shang-Hua (2007), "Spectral partitioning works: Planar graphs and finite element meshes", Linear Algebra and Its Applications , 421 (2–3): 284–305, doi : 10.1016/j.laa.2006.07.020
• Sykora, Ondrej; Vrt'o, Imrich (1993), "Edge separators for graphs of bounded genus with applications", Theoretical Computer Science , 112 (2): 419–429, doi : 10.1016/0304-3975(93)90031-N
• Tazari, Siamak; Müller-Hannemann, Matthias (2009), "Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation", Discrete Applied Mathematics , 157 (4): 673–684, doi : 10.1016/j. dam.2008.08.002
• Ungar, Peter (1951), "A theorem on planar graphs", Journal of the London Mathematical Society , 1 (4): 256, doi : 10.1112/jlms/s1-26.4.256
•   Weimann, Oren; Yuster, Raphael (2010), "Computing the girth of a planar graph in $O(n\log n)$ time", SIAM Journal on Discrete Mathematics , 24 (2): 609, CiteSeerX 10.1.1.156.5730 , doi : 10.1137/090767868
• Wulff-Nilsen, Christian (2009), Girth of a planar digraph with real edge weights in $O(n\log ^{3}n)$ time , arXiv : 0908.0697 , Bibcode : 2009arXiv0908.0697W