Síkgráf-elválasztási tétel

A matematika, azon belül a gráfelmélet területén a síkgráf-elválasztási tétel, síkgráf-felbontási tétel, síkgráf-szeparációs tétel vagy Lipton–Tarjan-szeparátortétel (planar separator theorem) a síkbarajzolható gráfokra vonatkozó egyfajta izoperimetrikus egyenlőtlenség, ami kimondja, hogy bármely síkbarajzolható gráf kis számú csúcs eltávolításával kisebb darabokra szedhető szét. Pontosabban, egy n csúcsú gráfból O(√n) csúcsot eltávolítva (ahol O a nagy Ordó jelölésre utal) a gráfot olyan diszjunkt részgráfokra bontja fel, melyek mindegyikében legfeljebb 2n/3 csúcs található.

A szeparációs tételnek először egy gyengébb változatát sikerült bizonyítania (Ungar 1951)-nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként (Lipton & Tarjan 1979) igazolta. Azóta a szeparátortételt sokféleképpen sikerült bizonyítani, a tételben szereplő O(√n) tagot javították és a tételt kiterjesztették a nem síkbarajzolható gráfok egyes osztályaira is.

A síkgráf-elválasztási tétel ismételt alkalmazása egy szeparátorhierarchiát hoz létre, ami a gráf fafelbontásának vagy elágazás-felbontásának (branch-decomposition) formáját öltheti. Ezek a szeparátorhierarchiák felhasználhatók síkgráfokon futtatott hatékony „oszd meg és uralkodj”-algoritmusok létrehozására, és az ezeken a hierarchiákon végzett dinamikus programozás segítségével ezen gráfok általában NP-nehéz optimalizációs problémáit exponenciális időben megoldó vagy rögzített paraméter mellett kezelhető algoritmusok előállítására. A szeparátorhierarchiákat használják a nested dissection (kb. „egymásba ágyazott boncolás”) módszerében is, ami a végeselemes módszerben fellépő ritka lineáris egyenletrendszerek megoldásának hatékony, Gauss-eliminációs variánsa.

Demaine, Fomin, Hajiaghayi és Thilikos bidimenzionalitás-elmélete a síkgráf-elválasztási tételt általánosítja és nagyban kiterjeszti az alkalmazási területét a síkbarajzolható gráfok rengeteg minimalizálási problémája mellett az egy-egy tiltott minort nem tartalmazó gráfokra.

A tétel kimondása

A tétel leggyakoribb megfogalmazásában úgy hangzik, hogy bármely G = (V,E) n csúcsú síkbarajzolható gráfhoz létezik G csúcsainak olyan három, A, S és B csúcshalmazba való particionálása, hogy akár A, akár B legfeljebb 2n/3 csúcsot tartalmaz, S-ben O(√n) csúcs van, és egyetlen A-beli csúcs sincs összekötve egyetlen B-beli csúccsal sem. Nem szükséges, hogy akár A, akár B a G gráf összefüggő részgráfjai legyenek. S-et a partíció szeparátorának nevezzük.

Egy ekvivalens megfogalmazás szerint bármely n csúcsú G síkbarajzolható gráf élei szétoszthatók a két éldiszjunkt részgráf, G₁ és G₂ között oly módon, hogy mindkét részgráf legalább n/3 csúcsot tartalmaz és a két részgráf csúcshalmazainak metszetében O(√n) csúcs található. Az ilyen szétosztást szeparációnak nevezzük. Ha adott egy szeparáció, a csúcshalmazok metszete szeparátort alkot, és az egyik részgráfba tartozó csúcsok, amik nem tartoznak a másik részgráfhoz alkotják a legfeljebb 2n/3 csúcsból álló szeparált csúcshalmazokat. A másik irányból tekintve, ha meg van adva a tételnek megfelelő A, S és B csúcshalmazba történő szeparálás, akkor létrehozható olyan szeparáció, melyben az A-ból kiinduló élek G₁-hez, a B-ből kiinduló élek G₂-höz tartoznak, a maradék éleket (melyeknek mindkét végpontja S-ben található) pedig tetszés szerint szétosztjuk.

A szeparátortételben szereplő 2/3 konstans önkényesen választott, bármely más számmal helyettesíthető az (1/2,1) nyílt intervallumban a tétel további megváltoztatása nélkül: egy nem annyira kiegyenlített felosztásból létrehozható egyenlőbb méretű részhalmazokra felosztás oly módon, hogy a kiegyenlítetlen felosztás nagyobbik halmazát ismételten felvagdossuk, majd átcsoportosítjuk az eredményül kapott összefüggő komponenseket.

Példa

Egy rácsgráf síkszeparátora.

Tekintsünk egy r sorból és c oszlopból álló rácsgráfot; a csúcsok n száma megegyezik rc-vel. Például az ábrán szereplő esetben r = 5, c = 8 és n = 40. Ha r páratlan, egyetlen középső sor van, egyébként két, a középponthoz egyformán közeli sor; hasonlóan, ha c páratlan, egyetlen középső oszlop van, egyébként pedig két, a középponthoz egyformán közeli oszlop. Ha az S-t ezen középső helyzetű sor(ok) vagy oszlop(ok) bármelyikének választjuk, S gráfból való eltávolításával két kisebb, összefüggő A és B részgráfot kapunk, melyek mindegyikében legfeljebb n/2 csúcs található. Ha, mint az ábrán, r ≤ c akkor a középső oszlop S szeparátora r ≤ √n csúcsból fog állni, hasonlóan, ha c ≤ r, akkor a középső sor szeparátorában legfeljebb √n csúcs lesz. Tehát minden rácsgráfnak van legfeljebb √n méretű S szeparátora, melynek eltávolítása a gráfot két, legfeljebb n/2 méretű összefüggő komponensre bontja.

A síkgráf-felbontási tétel állítása szerint ilyen felbontás bármely síkbarajzolható gráfhoz előállítható. Tetszőleges síkbarajzolható gráfot választva annyi különbséget találunk, hogy a szeparátor mérete O(√n), ami nagyobb lehet √n-nél, az A és B részhalmazok méretének korlátja (a tétel leggyakoribb verzióiban) n/2 helyett 2n/3, és az A és B részhalmazok nem feltétlenül alkotnak összefüggő részgráfokat.

Konstrukciók

Mélységi rétegzés

(Lipton & Tarjan 1979) adott síkbarajzolható gráfot szükség esetén további élekkel egészít ki, hogy maximális legyen (síkbarajzolásának minden tartománya háromszög). Ekkor tetszőleges v csúcsból kiindulva mélységi keresést folytat, és v-től való távolságuk alapján rétegekre particionálja a gráfot. Ha l₁ a medián szint (az a szint, amelynél lejjebb és följebb is legfeljebb n/2 csúcs található), akkor léteznie kell olyan l₀ és l₂ szinteknek O(√n) lépéssel l₁ alatt, illetve fölött, melyek O(√n)-O(√n) csúcsot tartalmaznak, különben több mint n csúcs lenne az l₁-közeli szinteken. Megmutatják, hogy léteznie kell egy S szeparátornak, ami előáll az l₀ és l₂ uniójából, egy G-beli e él végpontjaiból, melyek nem tartoznak a mélységi keresési fához és két szint között húzódnak, valamint az e-ből vissza az l₀ szintre húzódó két mélységi keresési fa-útvonal csúcsaiból. Az így kapott S szeparátor mérete legfeljebb √8√n, azaz körülbelül 2,83√n. A szeparátor csúcsai és két diszjunkt részgráf lineáris idő alatt előállítható.

A szeparátortétel ezen bizonyítása alkalmazható olyan súlyozott síkbarajzolható gráfokra is, melyek minden csúcsa nemnegatív költségű. A gráf particionálható A, S és B csúcshalmazokra oly módon, hogy A-ra és B-re külön-külön legfeljebb a teljes költség ⅔-a esik, S csúcsainak száma O(√n) és nem húzódik A és B között él. Egy hasonló szeparátor-konstrukció részletesebb vizsgálatával (Djidjev 1982) kimutatta, hogy S mérete √6√n-re, azaz körülbelül 2,45√n-re redukálható.

(Holzer et al. 2009) egyszerűsített megközelítést javasolnak: az előzővel megegyező módon kiegészítik a gráfot maximális síkgráffá és kialakítják a mélységi keresési fát. Ekkor minden, a fa részét nem képező e élhez kialakítanak egy kört oly módon, hogy e-t kombinálják a végpontjait összekötő útvonallal a fában. Bár ez a megközelítés nem garantálja, hogy nagy átmérőjű síkbarajzolható gráfokban kis szeparátort találjunk, a kísérletek szerint számos fajta síkgráfon jobb teljesítményt nyújt mind a Lipton–Tarjan-féle, mind a Djidjev-féle mélységi keresési módszereknél.

Egyszerű körszeparátorok

Olyan gráf esetében, ami eleve maximális síkbarajzolható, létezik egy erősebb konstrukció, az egyszerű körszeparátor (simple cycle separator), egy olyan nem túl nagyméretű kör, melynél a kör belső, illetve külső részén (a gráf egyedi síkba ágyazását tekintve) egyaránt legfeljebb 2n/3 csúcs található. Ezt az állítást (Miller 1986) igazolja (√8√n méretű szeparátorral), olyan, módosított Lipton–Tarjan-jellegű mélységi kereséssel, melyben a keresés szintjeiben egyszerű körök szerepelnek.

(Alon, Seymour & Thomas 1994) az egyszerű körszeparátorok létezését közvetlenebb módon igazolja: kiválasztanak egy olyan C kört, ami legfeljebb √8√n csúcsból áll, és amin kívül legfeljebb 2n/3 csúcs található, és a lehető legkiegyenlítettebb módon választja szét a külső és belső csúcsokat, majd megmutatják, hogy az előfeltételezésekből következik, hogy C szeparátor legyen. Máskülönben a C-n belüli távolságoknak meg kellene egyeznie a C által körülzárt korongban lévő távolságokkal (a korongon belüli rövidebb útvonalból ugyanis egy jobb kört lehetne alkotni). Ráadásul C hosszúságának pontosan √8√n-nek kell lennie, egyébként javítani lehetne valamely élének a háromszög két másik oldalára történő kicserélésével. Ha C csúcsait az óramutató járása szerint 1-től √8√n-ig megszámozzuk, és az i csúcsot a √8√n − i + 1 csúccsal párosítjuk, akkor ezek a párok a korongon belül csúcsdiszjunkt úttal összeköthetők, a Menger-tétel egy síkgráf-változata alapján. Az ilyen utak hossza azonban szükségképpen meghaladná n-et, amivel ellentmondásra jutunk. Egy hasonló módszer segítségével kimutatják, hogy létezik legfeljebb (3/√2)√n, azaz körülbelül 2,12√n méretű egyszerű körszeparátor.

(Djidjev & Venkatesan 1997) az egyszerű körszeparátor-tételben szereplő konstans faktort tovább javították 1,97√n-re. Módszerük szintén képes nemnegatív csúcs-súlyozott gráfokban egyszerű körszeparátorokat találni legfeljebb 2√n méretű szeparátorral, és kisebb szeparátorok előállítására is képes, a gráf kiegyensúlyozotlanabb particionálása árán. Kétszeresen összefüggő, nem maximális síkbarajzolható gráfokban léteznek olyan, közel lineáris időben megtalálható, egyszerű körszeparátorok, melyek mérete a tartományhosszúságok vektorának euklideszi normájával arányos.

Geometriai körszeparátorok

A körpakolási tétel szerint minden síkbarajzolható gráf reprezentálható diszjunkt belső részű korongok síkba elhelyezésével úgy, hogy a gráf két csúcsa akkor szomszédos, ha a nekik megfelelő korongok érintik egymást. Ahogy azt (Miller et al. 1997) megmutatta, minden ilyen pakoláshoz létezik olyan kör, ami a korongok közül legfeljebb 3n/4-et érint, vagy található azokon belül, a korongok közül legfeljebb 3n/4-et érint vagy található azokon kívül, és O(√n) korongon megy át.

Ennek bizonyításához Miller és tsai. sztereografikus projekcióval a körpakolást egy háromdimenziós egységgömbre vetítik. A projekció jó megválasztásával elérhető, hogy a gömb középpontja a felületén lévő korongok középpontjainak térbeli mediánja legyen, és így bármely, a középponton átmenő sík a gömböt két olyan féltérre bontsa, melyek bármelyike legfeljebb a korongok közül 3n/4-et foglal magába vagy metsz. Ha egyenlő valószínűséggel véletlenszerűen választunk egy középponton átmenő síkot, adott korong metszésének valószínűsége a korong sugarával lesz arányos. Így tehát a metszett korongok számának várható értéke a korongok sugarainak szummájával arányos. A sugarak négyzetösszege azonban a korongok teljes területével arányos, ami legfeljebb az egységgömb felszínével egyezhet meg, ami állandó. A Jensen-egyenlőtlenséget segítségül hívva megmutathatjuk, hogy amikor n nemnegatív valós szám négyzetösszegének egy konstans a korlátja, a számok összege O(√n). Tehát egy véletlenszerű síkkal elmetszett korongok számának várható értéke O(√n) és létezik olyan sík, ami legfeljebb ennyi korongot metsz. Ez a sík a gömböt egy főkörén metszi, ami visszavetíthető a síkba, mint egy a kívánt tulajdonságokkal rendelkező kör. A kör által metszett O(√n) korong azoknak a szeparátor csúcsoknak felel, amik elválasztják a kör belsejében található korongoknak megfelelő csúcsokat azoktól a csúcsoktól, amik a körön kívül lévő korongoknak felelnek meg, és mindkét halmazba legfeljebb 3n/4 csúcs tartozik.

Ez a módszer egy olyan véletlen algoritmushoz vezet, ami képes lineáris időben megtalálni egy szeparátort, és egy kevésbé praktikus determinisztikus algoritmushoz, ami ugyanúgy lineáris idejű. A körpakolások sűrűségére ismert korlátok analizálásával megmutatható, hogy lehetséges olyan szeparátorokat találni, melyek mérete legfeljebb

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

Bár ez a javított szeparátorméret a gráf particionálása kiegyenlítettségének rovására megy, (Spielman & Teng 1996) szerint így is javított konstans faktort tartalmaz az algoritmus idejét tekintve (Alon, Seymour & Thomas 1990) szeparátoraihoz képest. A gyakorlatban az algoritmus által előállított szeparátorok méretén lehet javítani, például a véletlenszerű vágó síkok esetében nem egyenletes eloszlást használva.

A Miller és tsai. módszerében szereplő sztereografikus projekció elkerülhető, ha vesszük a legkisebb kör, ami a korongok középpontjainak valamely konstans hányadát tartalmazza, majd kiterjesztjük egy az [1,2] intervallumból véletlenszerűen választott konstanssal. Könnyen beláthatók hogy épp úgy mint Miller és tsainál, a kiterjesztett kört metsző korongok érvényes szeparátort alkotnak, ami várhatóan a megfelelő méretű szeparátor. Az eredményül kapott konstansok azonban valamivel rosszabbak.

Spektrális particionálás

A spektrális klaszterezési technikákat, melyekben egy gráf csúcsait a gráfból nyert mátrix sajátvektorainak koordinátai szerint csoportosítják, jó ideje alkalmazzák nem síkbarajzolható gráfok felbontási problémái heurisztikájának. (Spielman & Teng 2007) megmutatta, hogy a spektrális klaszterezés alkalmas lehet a síkgráf-elválasztási tétel egy gyengébb, korlátos fokszámú változatának bizonyítására. Módszerük szerint az adott síkbarajzolható gráf csúcsait a gráf Laplace-mátrixa sajátvektorai második koordinátája szerint állítják sorba, és ezt a sorbaállítást azon a ponton particionálják, amely minimalizálja a partíció kisebbik felén lévő csúcsok által elvágott élek arányát. Megmutatják, hogy minden korlátos fokszámú síkbarajzolható gráfban létezik olyan, az előzőek szerinti particionálás, melyben az arány O(1/√n). Bár ez a felbontás nem feltétlenül kiegyensúlyozott, a két oldal közül a nagyobbikkal megismételve a felbontást és az ismétlések során létrejött vágások unióját képezve végül egy O(√n) élből álló kiegyensúlyozott partícióhoz jutunk. Ezen élek végpontjai O(√n) méretű szeparátort alkotnak.

Élszeparátorok

A síkgráf-elválasztási tétel egy változatában élszeparátorok szerepelnek, azaz olyan kis élhalmazok, melyek egy vágást alkotnak a gráf csúcsainak A és B részhalmazai között. A két halmaz, A és B egyike sem lehet nagyobb a gráf n csúcsának valamely konkrét hányadánál (hagyományosan mindkét halmaz legfeljebb 2n/3 méretű lehet) és a gráf minden csúcsa vagy az A, vagy a B halmazhoz tartozik. A szeparátor azokból az élekből áll, melyek egyik végpontja az A, másik végpontja a B halmazban van. Az élszeparátor méretére vonatkozó korlátok általában a gráf csúcsainak számától és a csúcsok fokszámától is függnek: az olyan síkbarajzolható gráfoknak – például a kerékgráfoknak és a csillaggráfoknak –, melyekben van egy n − 1 fokszámú csúcs (domináló csúcs), nincs szublineáris élből álló élszeparátoruk, hiszen bármely élszeparátornak tartalmaznia kellene az összes, az univerzális csúcsból a vágás másik részébe futó élt. Elmondható azonban, hogy minden, Δ maximális fokszámú síkbarajzolható gráfnak van O(√(Δn)) méretű élszeparátora.

Egy síkgráf duálisának egyszerű körszeparátora megfelel az eredeti gráf élszeparátorának. A (Gazit & Miller 1990)-féle egyszerű körszeparátor-tételt adott síkgráf duálisára alkalmazva megerősíthető az élszeparátor méretére vonatkozó O(√(Δn)) korlát, annak megmutatásával, hogy minden síkbarajzolható gráfnak van olyan élszeparátora, aminek mérete egyenesen arányos csúcsai fokszámai vektorainak euklideszi normájával.

(Papadimitriou & Sideri 1996) leír egy polinom idejű algoritmust a legkisebb élszeparátor megkeresésére; az algoritmus G-t két azonos méretű részgráfra osztja, feltéve, hogy G egy (legfeljebb konstans számú lyukkal tűzdelt) rácsgráf feszített részgráfja. Sejtésük szerint a probléma általános síkbarajzolható gráfokra NP-teljes, és megmutatják, hogy a probléma bonyolultsága ugyanakkora tetszőleges számú lyukkal tűzdelt rácsgráf feszített részgráfjaira, mint tetszőleges síkbarajzolható gráfokra.

Alsó korlátok

Egy ikozaéder lapjainak 100 háromszögből álló rácsra cserélésével kapott poliéder, (Djidjev 1982) alsó korlátot célzó konstrukciójának egy példája.

Egy √n × √n-es rácsgráfban az s < √n pontból álló S halmaz legfeljebb s(s − 1)/2 rácspontot tud közrefogni, ahol a maximum úgy érhető el, hogy a rács sarkához közel kiinduló átlóban helyezzük el S csúcsait. Tehát egy olyan szeparátor esetén, ami legalább n/3 pontot választ le a megmaradó rácsból, s-nek legalább √(2n/3)-nak, azaz kb. 0,82√n-nek kell lennie.

Léteznek olyan n-csúcsú síkbarajzolható gráfok (tetszőlegesen nagy n értékekre), melyekben bármely olyan S szeparátor, ami a maradék gráfot legfeljebb 2n/3 csúcsot tartalmazó részgráfokra bontja vertices, legalább √(4π√3)√n, azaz mintegy 1,56√n csúcsból áll. A konstrukcióban szerepet játszik egy gömbfelület konvex poliéderrel való közelítése, majd a poliéder lapjainak háromszögekből álló ráccsal való helyettesítése után a gömb felületére izoperimetrikus egyenlőtlenségek alkalmazása.

Szeparátorhierarchiák

Egy síkbarajzolható gráf szeparátorai egyfajta szeparátorhierarchiává állnak össze, ami egy kisebb gráfokra történő rekurzív felbontás. Egy szeparátorhierarchia előállhat egy bináris fa formájában, melynek gyökere reprezentálja magát a gráfot, a gyökér két közvetlen „gyerek” csúcsa pedig annak a két rekurzívan megkonstruált szeparátorhierarchiának a két gyökere, melyeket egy szeparátor A és B részhalmazának feszített részgráfjaiból kapunk.

Egy ilyen jellegű szeparátorhierarchia adja adott gráf fafelbontásának alapját, melyben a fa adott csomópontjához tartozó csúcshalmaz éppen a csomóponttól a fa gyökeréig vezető út szeparátorainak uniójával egyezik meg. Mivel a gráfok mérete a fa minden szintjén konstans faktorral csökken, a szeparátorok méretére vonatkozó felső korlátok szintén minden egyes szinten konstans faktorral csökkennek, így ezeken az útvonalakon a szeparátorok méretei mértani sort alkotnak O(√n)-ig. Tehát az így kialakított szeparátor szélessége O(√n), és alkalmas annak megmutatására, hogy minden síkbarajzolható gráf favastagsága (minimális fafelbontás szélessége) O(√n).

Ha a szeparátorhierarchiát közvetlenül állítanánk elő a bináris fán felülről lefelé haladva, a fa minden egyes csomópontjához tartozó feszített részgráfon lineáris idejű szeparátoralgoritmust futtatva, az összesen O(n log n) időt venne igénybe. Lehetséges azonban a teljes szeparátorhierarchia lineáris idejű előállítása is: a Lipton–Tarjan mélységi keresési megközelítést alkalmazva, megfelelő adatszerkezetek segítségével minden particionáló lépést szublineáris időben elvégezve.

Ha egy hasonló jellegű hierarchiát szerkesztünk, ami a szeparátorok helyett a szeparációkon alapul, és melyben a gyökér csomópont két gyereke annak a két rekurzívan megkonstruált hierarchiának a két gyökere, melyeket egy szeparáció G₁ és G₂ részgráfjaiból kapunk, akkor a teljes struktúra fafelbontás helyett elágazás-felbontást vagy ágfelbontást (branch-decomposition) alkot. Ebben a felbontásban bármely szeparációnak a szélességét a csomóponttól a fa gyökeréig vezető út szeparátorméreteinek összege korlátozza, tehát bármely így kapott elágazás-felbontás szélessége O(√n) és bármely síkbarajzolható gráf fafelbontásának szélessége O(√n). Bár sok kapcsolódó gráffelbontási probléma NP-teljes még síkbarajzolható gráfokra is, egy síkbarajzolható gráf minimális szélességű elágazás-felbontása polinom időben elvégezhető.

(Alon, Seymour & Thomas 1994) módszereit közvetlenebb módon alkalmazva az elágazás-felbontás konstrukciója során (Fomin & Thilikos 2006a) megmutatta, hogy egy síkbarajzolható gráf fafelbontásának szélessége legfeljebb 2,12√n, ugyanaz a konstans, ami Alon és tsai egyszerű körszeparátor-tételében is szerepel. Mivel minden gráfra igaz, hogy favastagsága legfeljebb a fafelbontás másfélszerese, ezért a síkbarajzolható gráfok favastagsága legfeljebb 3,18√n.

Más gráfosztályok

Egyes ritka gráfoknak nincsen szublineáris méretű szeparátoruk: egy expander gráfban a csúcsok valamely konstans hányadát törölve még mindig egyetlen összefüggő komponens marad.

Talán a legkorábbi ismert szeparátorokkal kapcsolatos tétel (Jordan 1869) eredménye, miszerint bármely fa egyetlen csúcs eltávolításával egyenként legfeljebb n/2 csúcsot tartalmazó részfákra bontható. Pontosabban az a csúcs rendelkezik ezzel a tulajdonsággal, ami minimalizálja a maximális komponensméretet; hiszen, ha nem rendelkezne vele, akkor az egyedi nagy részfában lévő szomszédja egy még jobb particionálást alkotna. Ugyanezt a technikát tetszőleges gráf fafelbontására alkalmazva megmutatható, hogy bármely gráfnak van olyan szeparátora, aminek mérete legfeljebb a favastagságával egyenlő.

Ha egy G gráf nem síkbarajzolható, de beágyazható egy g génuszú felületbe, akkor létezik O((gn)^1/2) csúcs nagyságú szeparátora. (Gilbert, Hutchinson & Tarjan 1984) ezt (Lipton & Tarjan 1979) érveléséhez hasonlóan bizonyítja. Mélységi keresési szintekre csoportosítják a gráf csúcsait, majd keresnek két olyan szintet, melynek eltávolításával legfeljebb egy, kis számú szintből álló, nagyméretű komponens marad. Ez a megmaradó komponens síkbarajzolhatóvá alakítható a génuszával arányos számú mélységi keresési útvonal eltávolításával, ami után a már ismert Lipton–Tarjan-módszer alkalmazható a megmaradt síkbarajzolható gráfra. Ez az eredmény az eltávolított két szint és a köztük lévő szintek száma közötti óvatos egyensúlyozásból következik. Ha bemenetként meg van adva egy gráfbeágyazás, a hozzá tartozó szeparátor lineáris időben előállítható. A g génuszú gráfoknak továbbá létezik legfeljebb O((gΔn)^1/2) méretű élszeparátora.

A korlátos génuszú gráfok a minorképzés műveletére zárt gráfcsaládot alkotnak, és bármely, minorzárt gráfcsaládra vonatkoznak szeparátortételek. Pontosabban, ha egy gráfcsaládnak h csúcs méretű tiltott minora van, akkor létezik O(h√n) csúcs méretű szeparátora, ami O(n^1 + ε) időben megtalálható tetszőleges ε > 0-ra.

Korongok metszetgráfja, ahol legfeljebb k = 5 korong fedi a sík bármely pontját.

A (Miller et al. 1997)-féle körszeparátor módszer általánosítható tetszőleges d-dimenziós gömbökből álló metszetgráfokra, melyek rendelkeznek azzal a tulajdonsággal, hogy a tér bármely pontja legfeljebb valamely konstans k számú gömbbel van fedésben, továbbá d-dimenziós k-legközelebbi szomszéd-gráfra, valamint a végeselemes hálók gráfjaira. Az így megszerkesztett gömbszeparátorok a bemeneti gráfot legfeljebb n(d + 1)/(d + 2) csúcs méretű részgráfokra particionálják. A szeparátorok mérete a k-szoros gömbmetszetgráfokra és a k-legközelebbi szomszéd-gráfokra O(k^1/dn^1 − 1/d).

Alkalmazások

„Oszd meg és uralkodj”-algoritmusok

A szeparátorfelbontások jó szolgálatot tesznek a síkbarajzolható gráfok problémái hatékony megoldását szolgáló „oszd meg és uralkodj”-algoritmusok előállításában. Ilyen eset például egy síkbarajzolható súlyozott irányított gráfban a legrövidebb kör megkeresése. Ez a következő lépésekben elvégezhető:

• Particionáljuk az adott G gráfot a síkgráf-elválasztási tétel szerint S, A és B részgráfokba
• Rekurzívan keressük meg A és B legrövidebb köreit
• A Dijkstra-algoritmussal minden S-beli s csúcsra keressük meg a G-ben s-en keresztülhaladó legkisebb kört.
• Adjuk vissza a fenti lépésekben talált legrövidebb kört.

Az algoritmus A-hoz és B-hez tartozó rekurzív hívásainak idejét főleg a Dijkstra-algoritmus O(√n)-szer történő meghívása dominálja, így tehát az algoritmus a legrövidebb kört O(n^3/2 log n) időben találja meg.

Ugyanennek a legrövidebb kör problémának egy gyorsabb, O(n log³n) időben futó megoldását adja (Wulff-Nilsen 2009). Az ő algoritmusa ugyanezt a szeparátor-alapú „oszd meg és uralkodj”-struktúrát használja, de tetszőlegesen választott szeparátorok helyett egyszerű körszeparátorokat alkalmaz, így az S csúcsai a körszeparátoron belül, illetve kívül található gráfok egyetlen tartományához tartoznak. Ekkor a Dijkstra-algoritmus O(√n)-szeri meghívása helyett körmönfontabb algoritmusokkal keresi meg a síkgráf egyetlen tartományának összes csúcsából kiinduló legrövidebb utakat, majd kombinálja őket a két részgráftól való távolságokkal. Súlyozott, de irányítatlan síkbarajzolható gráfok legrövidebb köre ekvivalens a duális gráf minimális vágásával, így O(n log log n) időben megtalálható, a súlyozatlan és irányítatlan síkbarajzolható gráf legrövidebb köre (azaz girthparamétere) pedig O(n) időben. (A súlyozatlan gráfoknál azonban a leggyorsabb algoritmus nem a szeparátortételen alapul.)

Frederickson 1986-ban egy másik gyorsabb algoritmussal állt elő az egyetlen forrásból kiinduló legrövidebb utak keresésére síkbarajzolható gráfokban a szeparátortételt felhasználva. Ez Dijkstra algoritmusának javított változata, ami csúcsok egy gondosan kiválasztott részhalmazán végez iteratív keresést. Ez a változat O(n √(log n)) időt vesz igénybe egy n-csúcsú gráf esetén. Szeparátorok segítségével megkeresi egy gráf „divízióját”, azaz az élhalmaz két vagy több részhalmazra, „régiókra” osztását. Egy csomópontot (csúcsot) akkor tartalmaz egy régió, ha a régió valamely éle illeszkedik a csúcsra. Az olyan csúcs, amit több régió tartalmaz, az őt tartalmazó régiók határhelyzetű csúcsa. A módszer az n csomópontú gráf r-divízióját taglalja, ami a gráf O(n/r) régióra történő felosztása, melyek mindegyike O(r) csomópontot tartalmaz, közöttük O(√r) határhelyzetű csomóponttal. Frederickson megmutatta, hogy egy r-divízió O(n log n) időben előállítható a szeparátortétel rekurzív alkalmazásával.

A problémát megoldó algoritmusának vázlatos működése a következő.

1. Előfeldolgozó fázis: a gráfot gondosan kiválasztott (csúcs-)részhalmazokra osztjuk, majd meghatározzuk az egyes részhalmazok elemei közötti legrövidebb utakat, ahol van az út köztes csúcsai között az adott részhalmazon kívül eső. Ebben a fázisban megtörténik a G₀  síkbarajzolható gráf átalakítása egy 3-nál nagyobb fokszámmal nem rendelkező G gráffá. Az Euler-formula egyik következményeként az eredményül kapott gráf csúcsainak száma n ≤ 6n₀ -12, ahol n₀  a G₀  csúcsainak száma. Ez a fázis garantálja továbbá az r-divízió a megfelelő tulajdonságait, a következők szerint. A síkbarajzolható gráf olyan r-divíziójáról van szó, melyben

• minden határhelyzetű csúcsot legfeljebb három régió tartalmaz;
• minden, nem összefüggő régió olyan összefüggő komponensekből áll, melyek mindegyikének pontosan ugyanazzal az egy vagy két összefüggő régióval vannak közös határhelyzetű csúcsai.

2. Keresési fázis:

• Fő löket („Main Thrust”): megkeressük a forrás és a részhalmaz egyes csúcsai közötti legrövidebb utak hosszát. Amikor a részhalmaz egy v csúcsát lezárjuk, d(w) értékét minden w csúcsra frissíteni kell abban a részhalmazban, melyben létezik v és w közötti út.
• Takarítás („Mop-up”): az összes többi csúcshoz vezető legrövidebb út hosszának meghatározása.

Henzinger és tsai. a Frederickson által a síkbarajzolható gráfokon „single source shortest path” (egy kezdőpontból az összes többi pontba vezető legrövidebb út) algoritmussal futtatott r-divíziós technikát kiterjesztették nemnegatív élhosszakra, és lineáris idejű algoritmust adtak meg. Módszerük a Frederickson-féle gráfdivízió fogalmának általánosítása oly módon, hogy egy n-csúcsú gráf (r,s)-divíziója a gráf felosztása O(n/r) régióra, melyek mindegyike r^{O(1)}  csúcsot tartalmaz és legfeljebb s határhelyzetű csúcsot. Ha egy (r, s)-divíziót ismételten kisebb régiókra osztunk, rekurzív divízióról beszélhetünk. Ez az algoritmus körülbelül log*n rekurziós szintet használ. A rekurzív divízió gyökeres faként jelenik meg, melynek levelei G egyes éleivel vannak címkézve. A fa gyökere jelképezi a teljes G-t tartalmazó régiót, a gyökér közvetlen leszármazottai a teljes G alrégióit és így tovább. Minden levél, avagy atomi régió pontosan egy élt tartalmaz.

A nested dissection (kb: „egymásba ágyazott boncolás”) a síkgráf-struktúrájú ritka, szimmetrikus lineáris egyenletrendszerek (melyek például a végeselemes módszerben jelennek meg) Gauss-eliminációs megoldására szolgáló, szeparátorhierarchiákon alapuló „oszd meg és uralkodj”-variáns. Alkalmazása során az egyenletrendszert leíró gráfban keresni kell egy szeparátort, majd a szeparátorral elválasztott két alprobléma változóit rekurzívan eliminálni kell, majd magának a szeparátornak a változóit is. Ennek a módszernek a feltöltődési értéke („fill-in”, a mátrix kapott Cholesky-felbontásában az újonnan keletkezett nemnulla elemek száma) alacsony, O(n log n), ami versenyképessé teszi a nested dissectiont az ugyanezen a problémán alkalmazott többi iteratív módszerrel.

Klein, Mozes és Weimann megadtak egy O(n log² n)-idejű, lineáris terű algoritmust, ami képes síkbarajzolható irányított gráfban egy s forrásból az összes csúcsba menő legrövidebb utak megállapítására, ahol a gráfban pozitív és negatív irányított élhosszúságok is megengedettek, de negatív értékű körök nem. Algoritmusuk síkgráf-szeparátorok segítségével keres egy C Jordan-görbét, ami O(√n) csúcson megy át (de egyetlen élt sem metsz) úgy, hogy n/3 és 2n/3 közötti csúcsot foglal magába. A csúcsok, amiken C átmegy, határhelyzetű csúcsok. Az eredeti G gráfot ekkor a G₀  és G₁  gráfokba választja ketté, a síkba ágyazást C mentén elvágva és a határhelyzetű csúcsokat megkettőzve. Az i = 0 és 1 értékekre G_i -ben a határhelyzetű csúcsok egyetlen F_i  tartomány határán helyezkednek el.

A Klein, Mozes és Weimann által alkalmazott megközelítés nagy vonalakban a következő:

• Rekurzív hívás: az első fokozat rekurzívan kiszámítja az r-től való távolságokat G_i-ben  i = 0, 1-re.
• Részen belüli határtávolságok (Intra-part boundary-distances): Minden G _i  gráfban kiszámítja a G_i  határhelyzetű csúcsai közötti összes távolságot. Ez O(n log n) időt vesz igénybe.
• Egy kezdőpontból mért részek közötti határtávolságok (Single-source inter-part boundary distances): Egy G-beli legrövidebb út váltakozik G₀  és G₁  között, hogy megállapíthassuk a G-beli, r-től az összes határhelyzetű csúcsig vezető távolságokat. Váltakozó iterációk során felhasználjuk a $G₀  és $G₁ -beli összes határhelyzetű távolságot. Az iterációk száma O(√n), így a fokozat teljes időigénye O(n α(n)), ahol α(n) az inverz Ackermann-függvény.
• Egy kezdőpontból mért részek közötti távolságok (Single-source inter-part distances): a korábbi fokozatokban kiszámított távolságokat használja fel egy Dijkstra-számításban minden egyes G_i  egy módosított változatán, ezzel kiszámítva a G-ben r-től az összes csúcsig a távolságokat. Ez a fokozat O(n log n) időt vesz igénybe.
• A kezdőponti távolságok új kezdőpontba helyezése (Rerooting single-source distances): a G-beli, r-től mért távolságok nemnegatív hosszokra transzformálása, majd Dijkstra algoritmusának ismételt felhasználásával az s-től való távolságok kiszámítása. Ez a fokozat O(n log n) időt vesz igénybe.

Az algoritmus fontos részét képezi az árfüggvények (price functions) és redukált hosszak (reduced lengths) használata. Egy ι(·),irányított élhosszakkal rendelkező G irányított gráfbeli árfüggvény olyan φ függvény, ami a G csúcsait a valós számokhoz rendeli. Egy uv irányított él φ szerinti redukált hossza, ιφ(uv) = ι(uv) + φ(u) − φ(v). Egy alkalmas árfüggvény olyan árfüggvény, ami G minden irányított élére nemnegatív redukált hosszakat állít elő. Haszna abban mutatkozik meg, hogy a pozitív és negatív hosszakat is tartalmazó legrövidebb út problémát kizárólag nemnegatív hosszakat tartalmazóra lehet vele konvertálni, ami aztán a Dijkstra-algoritmussal már megoldható.

A szeparátor-alapú „oszd meg és uralkodj”-paradigmát felhasználták dinamikus gráfalgoritmusok és pont helyzetének meghatározását szolgáló algoritmusok adatstruktúrájának tervezésében, sokszög háromszögekre bontására, illetve legrövidebb utak keresésére szolgáló algoritmusok tervezésében, legközelebbi szomszéd-gráfok konstruálásában, továbbá síkbarajzolható gráf maximális elemszámú független halmazát előállító közelítő algoritmusokban.

NP-nehéz optimalizálási problémák egzakt megoldása

Egy síkbarajzolható gráf fafelbontásán vagy ágfelbontásán dinamikus programozást alkalmazva számos NP-nehéz optimalizációs probléma√n vagy √n log n szerinti exponenciális időben megoldhatóvá válik.

Ilyen alakban megjelenő korlátok ismertek maximális elemszámú független halmazok, Steiner-fák és Hamilton-körök megkeresésére, valamint a síkbarajzolható gráfbeli utazó ügynök-probléma megoldására. Hasonló, geometrikus gráfokra vonatkozó szeparátortételeket alkalmazó módszerekkel hasonló időkorlátok alatt oldhatók meg az euklideszi utazó ügynök-problémák és Steiner-fa problémák is.

Olyan parametrizált problémák esetében, melyek a síkbarajzolhatóság megtartásával és a bemeneti gráf méretének lineáris függvénye szerinti méretű kernellel előfeldolgozhatók, ezzel a megközelítéssel olyan, rögzített paraméter mellett kezelhető algoritmusok tervezhetők, melyek futásideje a bemeneti gráf méretének polinom, √k-nak pedig exponenciális függvénye, ahol k az algoritmus paramétere. Ilyen alakú időkorlátok ismertek a k méretű csúcslefedések és domináló halmazok megkeresésére.

Approximációs algoritmusok

(Lipton & Tarjan 1980) megfigyelése szerint a szeparátortétel segítségével síkbarajzolható gráfok NP-nehéz optimalizációs problémáira, mint amilyen a maximális elemszámú független halmaz keresése előállíthatók polinomiális approximációs sémák. Konkrétan, egy szeparátorhierarchia megfelelő szinten történő csonkolásával olyan, O(n/√log n) méretű szeparátor található, aminek eltávolítása a gráfot c log n méretű részekre bontja, bármilyen c konstansra. A négyszíntétel alapján léteznie kell legalább n/4 méretű független csúcshalmaznak, ezért az eltávolított csúcsok a maximális elemszámú független halmaz elhanyagolható részét adják, és a maradék részgráfok maximális elemszámú független halmazai függetlenül, méretük szerinti exponenciális időben megtalálhatók. Ezt a megközelítést kombinálva a későbbi, lineáris idejű szeparátorhierarchia-előállítási módszerekkel és az izomorf részgráfok független halmazainak számítását elősegítő, táblázatból történő kikereséssel, lehetőség nyílik az optimális mérettől legfeljebb 1 − O(1/√log n) faktorral eltérő független halmazok lineáris idejű előállítására. Ennél a faktornál 1-hez még közelebb lévő approximációs arány érhető el (Baker 1994) későbbi megközelítésével (ami fafelbontáson alapul, de nem használ síkszeparátorokat), ami jobb egyensúlyozást tesz lehetővé az idő és az approximáció minősége között.

Hasonló, szeparátoralapú approximációs megoldásokat vetettek be más nehéz problémák, például a csúcslefedés-probléma közelítő kiszámítására. (Arora et al. 1998) a szeparátorokat másként használva approximálják a súlyozott síkbarajzolható gráfok legrövidebb út-metrikájának utazó ügynök-problémáját; algoritmusuk dinamikus programozással keresi meg azt a legrövidebb bejárást, ami a szeparátorhierarchia minden egyszer szintjén a szeparátoron korlátozott számban halad át, majd megmutatják, hogy az áthaladások korlátjának növekedésével az így konstruált bejárások az optimális bejárás hosszúságát approximálják.

Gráftömörítés

Síkbarajzolható gráfok és más, szeparálható gráfok esetén szeparátorokat használó adattömörítési algoritmusok kisebb tárterületen ábrázolhatják. Az ilyen algoritmusok működésének lényege, hogy egy k szám kiválasztása után az adott síkbarajzolható gráfot szeparátorokkal ismételten O(n/k) darab, legfeljebb k méretű részgráfra osztjuk, ahol maguk a szeparátorok O(n/√k) csúcsot tartalmaznak. A k értékének alkalmas megválasztásával (legfeljebb n logaritmusával arányos legyen) a nem izomorf k-csúcsú síkbarajzolható részgráfok száma lényegesen kisebb a felbontásban szereplő részgráfok számánál, tehát a gráf tömöríthető oly módon, hogy létrehozzuk a lehetséges nem izomorf részgráfok táblázatát, majd a szeparátor-dekompozíció részgráfjait a táblázatbeli indexeivel reprezentáljuk. A gráf a szeparátorcsúcsok alkotta maradék része letárolható akár direkten, akár az imént említett rekurzív adatstruktúrát használva. Ezzel a módszerrel a síkbarajzolható gráfok és néhány egyéb korlátozott gráfosztály információelméleti szempontból optimális számú biten eltárolható: ha az ábrázolandó gráfcsaládban P_n darab n-csúcsú gráf található, akkor a család egy-egy gráfja mindössze (1 + o(n))log₂P_n bittel ábrázolható. Ugyanilyen logika mentén felépített reprezentáció segítségével olyan konstans idejű lekérdezések is lehetségesek, mint a csúcsok közötti szomszédosságnak és a csúcsok fokszámának vizsgálata, valamint a szomszédos csúcsok listázása; ezt a részgráfok táblázatának további információkkal való kiegészítése teszi lehetővé.

Univerzális gráfok

Egy F gráfcsalád univerzális gráfja olyan gráf, ami az F család minden tagját részgráfként tartalmazza. Szeparátorok segítségével megmutatható, hogy megmutatható, hogy az n-csúcsú síkgráfoknak vannak univerzális gráfjai O(n^3/2).

A konstrukcióhoz szükséges egy olyan, erősebb alakra hozott szeparátortétel, melyben a szeparátor három csúcshalmazának méretei nem függnek a gráf szerkezetétől: létezik olyan c szám, melynek nagysága legfeljebb √n konstansszorosa, hogy minden n-csúcsú síkbarajzolható gráf felosztható A, S és B részhalmazokba, ahol A és B között nem mennek élek, ahol |S| = c és ahol |A| = |B| = (n − c)/2. Ez megmutatható a szokásos szeparátortétel újra és újra alkalmazásával a gráfra egészen addig, míg a partíció összes komponense elosztható két, n/2-nél kevesebb csúcsot tartalmazó részhalmazba, majd ezekből addig mozgatva csúcsokat a szeparátorba, míg az el nem éri a megadott méretet.

Miután ez az erősebb alakú szeparátortétel előállt, felhasználásával előállítható az n-csúcsú síkbarajzolható gráfok olyan szeparátorhierarchiája, ami szintén nem függ a gráfok szerkezetétől: az ebből a hierarchiából képzett fafelbontás szélessége O(√n) és bármilyen síkbarajzolható gráfhoz használható. Ebben a fafelbontásban azon csúcspárok halmaza, melyek a fafelbontás közös csomópontjához tartoznak, egy O(n^3/2) csúcsú triviálisan perfekt gráfot alkot, mely minden n-csúcsú síkbarajzolható gráfot tartalmaz részgráfként. Egy hasonló jellegű konstrukció megmutatja, hogy a korlátos fokszámú síkbarajzolható gráfok O(n log n) élszámú univerzális gráffal rendelkeznek, ahol az O jelölésben elrejtett konstans a fokszámkorláttól függ. Bármely, síkbarajzolható gráfokhoz (vagy akár nem korlátos fokszámú fákhoz) tartozó univerzális gráfnak rendelkeznie kell Ω(n log n) éllel, de az nem ismeretes, hogy akár ez az alsó korlát, akár az O(n^3/2) felső korlát éles-e tetszőleges síkbarajzolható gráf univerzális gráfjaira.

Fordítás

• Ez a szócikk részben vagy egészben a Planar separator theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• 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", J. Amer. Math. Soc. 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 et al. (1998), "A polynomial-time approximation scheme for weighted planar graph TSP", Proc. 9th ACM-SIAM Symposium on Discrete algorithms (SODA '98), pp. 33–41, <http://portal.acm.org/citation.cfm?id=314613.314632>.
• Babai, L.; Chung, F. R. K. & Erdős, P. et al. (1982), "On graphs which contain all sparse graphs", in Rosa, Alexander; Sabidussi, Gert & Turgeon, Jean, Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday, vol. 12, Annals of Discrete Mathematics, pp. 21–26, <http://renyi.hu/~p_erdos/1982-12.pdf>.
• 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.
• Bar-Yehuda, R. & Even, S. (1982), "On approximating a vertex cover for planar graphs", Proc. 14th ACM Symposium on Theory of Computing (STOC '82), pp. 303–309, ISBN 0-89791-070-2, DOI 10.1145/800070.802205.
• 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 R. K. & Leighton, F. T. et al. (1989), "Universal graphs for bounded-degree trees and planar graphs", SIAM Journal on Discrete Mathematics 2 (2): 145, doi:10.1137/0402014, <http://www.math.ucsd.edu/~fan/mypaps/fanpap/116universal.pdf>.
• Blandford, Daniel K.; Blelloch, Guy E. & Kash, Ian A. (2003), "Compact representations of separable graphs", Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA '03), pp. 679–688, <http://www.cs.cornell.edu/~kash/papers/BBK03.pdf>.
• Blelloch, Guy E. & Farzan, Arash (2010), "Succinct representations of separable graphs", in Amir, Amihood & Parida, Laxmi, Proc. 21st Symposium on Combinatorial Pattern Matching, vol. 6129, Lecture Notes in Computer Science, Springer-Verlag, pp. 138–150, ISBN 978-3-642-13508-8, DOI 10.1007/978-3-642-13509-5_13.
• Chalermsook, Parinya; Fakcharoenphol, Jittat & Nanongkai, Danupon (2004), "A deterministic near-linear time algorithm for finding minimum cuts in planar graphs", Proc. 15th ACM–SIAM Symposium on Discrete Algorithms (SODA'04), pp. 828–829, <http://chalermsook.googlepages.com/mincut.ps>.
• Chang, Hsien-Chih & Lu, Hsueh-I (2011), "Computing the girth of a planar graph in linear time", SIAM Journal on Computing 42: 1077–1094, DOI 10.1137/110832033.
• Chiba, Norishige; Nishizeki, Takao & Saito, Nobuji (1981), "Applications of the Lipton and Tarjan planar separator theorem", J. Inform. Process 4 (4): 203–207, <http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0427-11.pdf>.
• Chung, Fan R. K. (1990), "Separator theorems and their applications", in Korte, Bernhard; Lovász, László & Prömel, Hans Jürgen et al., Paths, Flows, and VLSI-Layout, vol. 9, Algorithms and Combinatorics, Springer-Verlag, pp. 17–34, ISBN 978-0-387-52685-0, <http://www.math.ucsd.edu/~fan/mypaps/fanpap/117separatorthms.pdf>.
• 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, H. N. & Sýkora, O. et al. (1993), "Edge separators of planar and outerplanar graphs with applications", Journal of Algorithms 14 (2): 258–279, DOI 10.1006/jagm.1993.1013.
• Djidjev, H. N. (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.
• Donath, W. E. & Hoffman, A. J. (1972), "Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices", IBM Techn. Disclosure Bull. 15: 938–944. As cited by (Spielman & Teng 2007).
• Dorn, Frederic; Penninkx, Eelko & Bodlaender, Hans L. et al. (2005), "Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions", Proc. 13th European Symposium on Algorithms (ESA '05), vol. 3669, Lecture Notes in Computer Science, Springer-Verlag, pp. 95–106, ISBN 978-3-540-29118-3, DOI 10.1007/11561071_11.
• Eppstein, David; Galil, Zvi & Italiano, Giuseppe F. et al. (1996), "Separator based sparsification. I. Planarity testing and minimum spanning trees", Journal of Computer and System Sciences 52 (1): 3–27, DOI 10.1006/jcss.1996.0002.
• Eppstein, David; Galil, Zvi & Italiano, Giuseppe F. et al. (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, <http://www.ics.uci.edu/~eppstein/pubs/EppMilTen-FI-95.ps.gz>.
• Erdős, Paul; Graham, Ronald & Szemerédi, Endre (1976), "On sparse graphs with dense long paths", Computers and mathematics with applications, Oxford: Pergamon, pp. 365–369, <http://www.renyi.hu/~p_erdos/1976-26.pdf>.
• Fiedler, Miroslav (1973), "Algebraic connectivity of graphs", Czechoslovak Math. J. 23 (98): 298–305. As cited by (Spielman & Teng 2007).
• Fomin, Fedor V. & Thilikos, Dimitrios M. (2006a), "New upper bounds on the decomposability of planar graphs", Journal of Graph Theory 51 (1): 53–81, doi:10.1002/jgt.20121, <http://users.uoa.gr/~sedthilk/papers/planar.pdf>.
• 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/S0097539702419649.
• Frieze, Alan; Miller, Gary L. & Teng, Shang-Hua (1992), "Separator based parallel divide and conquer in computational geometry", Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA '92), pp. 420–429, ISBN 0-89791-483-X, doi:10.1145/140901.141934, <http://www.math.cmu.edu/~af1p/Texfiles/sep.pdf>.
• Gazit, Hillel & Miller, Gary L. (1990), "Planar separators and the Euclidean norm", Proc. International Symposium on Algorithms (SIGAL'90), vol. 450, Lecture Notes in Computer Science, Springer-Verlag, pp. 338–347, ISBN 978-3-540-52921-7, doi:10.1007/3-540-52921-7_83, <http://www.cs.cmu.edu/~glmiller/Publications/Papers/GaMi90.pdf>.
• 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.
• 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.
• Gilbert, John R. & Tarjan, Robert E. (1986), "The analysis of a nested dissection algorithm", Numerische Mathematik 50 (4): 377–404, DOI 10.1007/BF01396660.
• Goodrich, Michael T. (1995), "Planar separators and parallel 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", Journal of Combinatorial Optimization 1 (1): 79–104, doi:10.1023/A:1009763020645, <http://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiTe94.pdf>.
• Har-Peled, Sariel (2011), A Simple Proof of the Existence of a Planar Separator.
• He, Xin; Kao, Ming-Yang & Lu, Hsueh-I (2000), "A fast general methodology for information-theoretically optimal encodings of graphs", SIAM Journal on Computing 30 (3): 838–846, DOI 10.1137/S0097539799359117.
• Holzer, Martin; Schulz, Frank & Wagner, Dorothea et al. (2009), "Engineering planar separator algorithms", Journal of Experimental Algorithmics 14: 1.5–1.31, doi:10.1145/1498698.1571635, <http://digbib.ubka.uni-karlsruhe.de/eva/ira/2005/20> Archiválva 2012. március 6-i dátummal a Wayback Machine-ben.
• Jordan, Camille (1869), "Sur les assemblages des lignes", Journal für die reine und angewandte Mathematik 70: 185–190, As cited by (Miller et al. 1997), <http://resolver.sub.uni-goettingen.de/purl?GDZPPN002153998>.
• Kawarabayashi, Ken-Ichi & Reed, Bruce (2010), "A separator theorem in minor-closed classes", Proc. 51st Annual IEEE Symposium on. Foundations of Computer Science.
• Klein, Philip; Rao, Satish & Rauch, Monika et al. (1994), "Faster shortest-path algorithms for planar graphs", Proc. 26th ACM Symposium on Theory of Computing (STOC '94), pp. 27–37, ISBN 0-89791-663-8, DOI 10.1145/195058.195092.
• Łącki, Jakub & Sankowski, Piotr (2011), "Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time", Proc. 19th Annual European Symposium on Algorithms, vol. 6942, Lecture Notes in Computer Science, Springer-Verlag, pp. 155–166, ISBN 978-3-642-23718-8, DOI 10.1007/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.
• 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.
• Miller, Gary L. (1986), "Finding small simple cycle separators for 2-connected planar graphs", Journal of Computer and System Sciences 32 (3): 265–279, doi:10.1016/0022-0000(86)90030-9, <http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi87.pdf>.
• Miller, Gary L.; Teng, Shang-Hua & Thurston, William et al. (1997), "Separators for sphere-packings and nearest neighbor graphs", J. ACM 44 (1): 1–29, DOI 10.1145/256292.256294.
• Miller, Gary L.; Teng, Shang-Hua & Thurston, William et al. (1998), "Geometric separators for finite-element meshes", SIAM Journal on Scientific Computing 19 (2): 364–386, DOI 10.1137/S1064827594262613.
• Pach, János & Agarwal, Pankaj K. (1995), "Lipton–Tarjan Separator Theorem", Combinatorial Geometry, John Wiley & Sons, pp. 99–102.
• Papadimitriou, C. H. & Sideri, M. (1996), "The bisection width of grid graphs", Theory of Computing Systems 29 (2): 97–110, DOI 10.1007/BF01305310.
• Plotkin, Serge; Rao, Satish & Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pp. 462–470, <http://portal.acm.org/citation.cfm?id=314625>.
• Reed, Bruce & Wood, David R. (2009), "A linear-time algorithm to find a separator in a graph excluding a minor", ACM Transactions on Algorithms 5 (4): 1–16, DOI 10.1145/1597036.1597043.
• Seymour, Paul D. & Thomas, Robin (1994), "Call routing and the ratcatcher", Combinatorica 14 (2): 217–241, DOI 10.1007/BF01215352.
• Smith, Warren D. & Wormald, Nicholas C. (1998), "Geometric separator theorems & applications", 39th Annual Symposium on Foundations of Computer Science (FOCS '98), November 8-11, 1998, Palo Alto, California, USA, IEEE Computer Society, pp. 232–243, DOI 10.1109/SFCS.1998.743449.
• Spielman, Daniel A. & Teng, Shang-Hua (1996), "Disk packings and planar separators", Proc. 12th ACM Symposium on Computational Geometry (SCG '96), pp. 349–358, ISBN 0-89791-804-5, doi:10.1145/237218.237404, <http://www.cs.yale.edu/homes/spielman/PAPERS/planarSep.pdf>.
• 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.
• Sýkora, Ondrej & Vrť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, DOI 10.1137/090767868.
• Wulff-Nilsen, Christian (2009), Girth of a planar digraph with real edge weights in O(n log³n) time.

Kapcsolódó szócikkek

• Elvágó csúcshalmaz
• Geometriai szeparátor