Síkbarajzolható gráf

Példagráfok
Síkbarajzolható	Síkba nem rajzolható
Pillangógráf	K₅ Teljes gráf
K₄ Teljes gráf	K_3,3 Három ház–három kút-gráf

A matematika, azon belül a gráfelmélet területén egy síkbarajzolható gráf olyan gráf, melynek létezik a síkba való beágyazása, tehát lerajzolható úgy a síkon, hogy élei kizárólag a csúcspontokban találkoznak (metszési száma 0), vagy más megfogalmazásban, lerajzolható a síkban anélkül, hogy élei metszenék egymást.^[1]

A gráf ilyen lerajzolása a síkgráf (plane graph), avagy a gráf síkra rajzolása, síkba ágyazása (planar embedding of the graph). Egy síkgráf meghatározható úgy is, hogy egy síkbarajzolható gráf minden csúcsához hozzárendeljük a sík egy pontját, minden éléhez pedig olyan síkgörbét, melynek végpontjai az él két csúcsához rendelt síkbeli pontok, és a síkgráfhoz tartozó görbék a végpontjaiktól eltekintve diszjunktak. Néha síkbarajzolható gráf helyett is a síkgráf kifejezést használják.

Sztereografikus projekcióval igazolható, hogy egy gráf akkor és csak akkor síkbarajzolható, ha gömbre rajzolható. A Fáry–Wagner-tétel szerint egy síkba rajzolható egyszerű gráf úgy is síkba rajzolható, hogy élei egyenes szakaszok.

A síkgráfok kombinatorikus térképekkel is reprezentálhatóak.

A topologikusan ekvivalens gömbre rajzolások ekvivalenciaosztályát síktérképnek (planar map) nevezik. Bár egy síkgráf rendelkezik külső vagy nem korlátos tartománnyal, a síktérkép egyik tartományának sincs megkülönböztetett státusza.

A síkbarajzolható gráfok általánosítása az adott génuszú (nemszámú) felületre rajzolható gráfok. Ezen terminológia szerint a síkba rajzolható gráfok nemszáma 0, mivel a sík (és a gömb) 0 nemszámú felületek. Lásd még: gráf beágyazása.

Kuratowski és Wagner tétele

Kazimierz Kuratowski lengyel matematikus a síkbarajzolható gráfok tiltott gráfok szerinti osztályozását adta, mely Kuratowski-tétel néven ismeretes:

Egy véges gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, amely topologikusan izomorf

K_{5}

-tel (az ötcsúcsú teljes gráffal) vagy

K_{3,3}

-mal (az ún. három ház–három kút gráffal).

A topologikus izomorfia tetszőleges számú csúcs elhagyását vagy él felosztását teszi lehetővé (például a •——• él változtatását erre: •—•—•).

A Wagner-tétel felosztások helyett minorokkal foglalkozik:

Egy véges gráf akkor és csak akkor síkbarajzolható, ha sem a

K_{5}

, sem a

K_{3,3}

nem minora.

Animáció, mely megmutatja, hogy a Petersen-gráf minorként tartalmazza a K_3,3 gráfot

Klaus Wagner általánosabb kérdése az volt, hogy vajon bármely minorképzés műveletére zárt gráfosztály meghatározható-e tiltott minorok véges halmazával. A válasz igen, az eredményt tanulmányok hosszú sorában bizonyították, és Robertson–Seymour-tétel néven ismeretes. A tétel nyelvezete szerint a véges síkbarajzolható gráfok tiltott minorai a K₅ és a K_3,3.

Egyéb síkbarajzolhatósági kritériumok

A gyakorlatban nem túl hatékony a Kuratowski-féle kritériumok alapján eldönteni, hogy adott gráf síkba rajzolható-e. Léteznek azonban gyors algoritmusok is erre a problémára: egy n csúcsú gráf esetében O(n) (lineáris idő) alatt eldönthető, hogy a gráfnak létezik-e síkba rajzolása (lásd Síkgráfság tesztelése).

Egy összefüggő, egyszerű síkbarajzolható gráf, mely v csúccsal és e éllel rendelkezik, igazak a következők:

1. tétel. Ha v ≥ 3, akkor e ≤ 3v − 6;

2. tétel. Ha v ≥ 3 és nincsenek 3 hosszúságú körök, akkor e ≤ 2v − 4.

Az 1. tétel bizonyítása: rajzoljuk le $G$ -t síkba. Mivel a gráf egyszerű, minden tartományát legalább 3 él határolja, ugyanakkor egy él legfeljebb két tartományt határolhat. Összegezzük minden tartományra az őket határoló élek számát. Az előbbiek miatt ez az érték legalább $3t$ , legfeljebb $2e$ . Tehát $3t\leq 2e$ , felhasználva az Euler-formulát, $3(e-v+2)\leq 2e$ . Ezt az egyenlőtlenséget átrendezve adódik, hogy $e\leq 3v-6$ . A 2. tétel igazolása hasonló gondolatmenettel történhet, mint az előzőé, figyelembe véve, hogy most minden tartományt legalább 4 él határol. Ebből adódik, hogy $4t\leq 2e$ és az Euler-formula alkalmazásával, hogy $e\leq 2v-4$ .

A fenti kritériumok szerint a síkgráfok ritka gráfok, mivel csak O(v) éllel rendelkeznek, aszimptotikusan jóval kevesebbel a maximális O(v²)-nél. Tekintsük például a K_3,3 gráfot, melynek 6 csúcsa és 9 éle van, de nem tartalmaz 3 hosszúságú kört. Ezért a 2. tétel értelmében nem lehet síkgráf. Jegyezzük meg, hogy ezek a tételek a síkba rajzolhatóságnak szükséges, de nem elégséges feltételeit adják meg, ezért csak egy gráf síkba rajzolhatóságának cáfolatára használhatók. Ha az 1. és a 2. tétel is kevésnek bizonyul, más módszereket kell keresni.

A Whitney-féle síkgráfkritérium a grafikus matroidok duálisának létezésén alapuló karakterizáció;
A Mac Lane-féle síkgráfkritérium a véges síkgráfok algebrai jellemzését adja, körterei alapján;
A Fraysseix–Rosenstiehl-féle síkgráfkritérium a mélységi keresés kográf-fa élei kétfelé particionálásának létezésére alapoz jellemzést. A bal-jobb síkgráfteszt-algoritmus alapját képezi;
A Schnyder-tétel a szomszédsági részbenrendezés dimenziószáma alapján adja a síkba rajzolhatóság karakterizációját;
A Colin de Verdière-síkgráfkritérium a gráf által meghatározott bizonyos Schrödinger-operátorai második sajátértékeinek maximális multiplicitása alapján jellemzi a síkbarajzolható gráfokat.
A Hanani–Tutte-tétel állítása szerint egy gráf pontosan akkor síkgráf, ha van olyan lerajzolása, melyben a független élpárok páros alkalommal metszik egymást; ezzel és egy modulo 2 egyenletrendszerrel jellemezhetők a síkbarajzolható gráfok.

Euler-formula

Bővebben: Euler-karakterisztika#Síkgráfok

Az Euler-formula azt mondja ki, hogy ha adott egy véges összefüggő síkgráf, és v a csúcsok, e az élek, f (faces) pedig a tartományok (élekkel határolt területek, beleértve a külső, végtelen nagy területet is) száma, akkor

v-e+f=2

.

Például a fenti pillangógráf esetében v = 5, e = 6 és f = 3. A K₄ teljes gráf esetében v = 4, e = 6 és f = 4. Általában igaz, hogy ha minden f tartománnyal rendelkező síkgráfra igaz a tulajdonság, egy olyan változtatás, ami új tartományt hoz létre, de a gráfot síkgráfként megtartja, a v − e + f értékét nem változtatja. Mivel a tulajdonság igaz minden f = 2 gráfra, teljes indukció alapján minden esetre igaz. Az Euler-formula így is igazolható: először vegyük észre, hogy minden belső, korlátos tartományt a gráf egy köre határol. Ebből adódik, hogy egy síkba rajzolt fának csak egy tartománya van, ez a külső, nem korlátos tartomány. Tudjuk, hogy minden fának 1-gyel kevesebb éle van, mint ahány csúcsa. Egyszerű számolással adódik, hogy a fákra teljesül az Euler-formula. Most bebizonyítjuk az állítást a kört tartalmazó, összefüggő gráfokra is. Tekintsük a gráf valamely körének egy $m$ -mel jelölt élét. Ez az él határa egy a körön belüli és egy a körön kívüli tartománynak. Az $m$ él elhagyásával a két tartomány egyesül. Tehát az élek és a tartományok száma egyaránt 1-gyel csökken, míg a csúcsok száma nem változik. Így ha az új gráfra teljesül az Euler-formula, akkor az eredetire is. Az eljárást (egy körbeli él elhagyása) folytassuk addig, ameddig a gráfban nem marad kör. Ekkor a gráf egy feszítőfájához jutunk, amelyre teljesül a formula, tehát az eredeti gráfra is.

Véges, összefüggő egyszerű síkgráfban a külső tartomány kivételével minden tartományt legalább három él határol, és minden él legfeljebb két tartománnyal szomszédos; az Euler-formula alapján megmutatható, hogy ezek a gráfok ritkák, abban az értelemben, hogy ha v ≥ 3:

e\leq 3v-6

.

Az Euler-formula konvex poliéderekre is érvényes. Ez nem véletlen: minden konvex poliéder átalakítható egy összefüggő, egyszerű síkgráffá a poliéder Schlegel-diagramja segítségével, ami a poliéder perspektivikus vetítése egy síkra, ahol a vetítés középpontja a poliéder valamely lapjának a közepéhez van közel. Nem minden síkgráf feleltethető meg egy komplex poliédernek: például egyetlen fa sem. A Steinitz-tétel kimondja, hogy a konvex poliéderekből képezett poliédergráfok pontosan a 3-szorosan összefüggő egyszerű síkba rajzolható gráfok. Általánosabban, az Euler-képlet minden olyan poliéderre vonatkozik, melynek felülete a gömbbel topolológiailag izomorf, tekintet nélkül arra, hogy konvex-e.

Nem összefüggő gráfokra

Az Euler-formula síkbarajzolható, egyszerű, $k$ összefüggő komponensből álló gráfokra a következőképpen módosul: $v+f=e+k+1$ , ahol $v$ a csúcsok, $f$ a tartományok, $e$ az élek számát jelöli.^[2]

Átlagos fokszám

A $v-e+f=2$ és $2e\geq 3f$ (egy tartományt legalább 3 él határol, egy él legfeljebb 2 tartományhoz tartozik) összefüggésekből algebrai átalakítások után következik, hogy a véges, síkba rajzolható gráfok átlagos fokszáma 6-nál kisebb.

Érmegráfok

Bővebben: Körpakolási tétel

A síkban két simulókör pontosan egy pontban metszi egymást. Egy „érmegráf” egymás belső területét át nem fedő körök által alkotott érintőgráf, ahol a gráf minden csúcsa egy körnek felel meg, és két kör érintkezésekor a körökhöz tartozó csúcsok között él húzódik. A Paul Kobe által 1936-ban bizonyított körpakolási tétel szerint egy gráf pontosan akkor síkbarajzolható, ha érmegráf.

Az eredmény felhasználásával könnyű bizonyítás adódik a Fáry-tételre, ami kimondja, hogy ha egy gráf síkbarajzolható, akkor ez megtörténhet egyenes szakaszok használatával is. Ha a gráf csúcsait az érmegráf-reprezentáció megfelelő köreinek középpontjába helyezzük, az érintő körök középpontjai között húzódó egyenes szakaszok nem metszenek egyetlen más szakaszt sem.

Kapcsolódó gráfcsaládok

Maximális síkgráfok

Egy egyszerű gráf akkor maximális síkbarajzolható gráf, ha síkba rajzolható, de tetszőleges él hozzáadása után elveszítené ezt a tulajdonságát. Ekkor minden tartományát (a külsőt is beleértve) három él határolja, ami megmagyarázza az alternatív plane triangulation („síkháromszögelés”) elnevezést. A „háromszögelt gráf” (triangular graph^[3] vagy triangulated graph)^[4] elnevezéseket inkább a teljes gráfok élgráfjaira és a merev körű gráfokra szokás alkalmazni. Minden maximális síkgráf 3-szorosan csúcsösszefüggő.

Ha egy maximális síkbarajzolható gráf v > 2 csúccsal rendelkezik, akkor pontosan 3v − 6 éle és 2v − 4 tartománya van.

Az Apollóniusz-hálózatok olyan maximális síkbarajzolható gráfok, melyek háromszögű tartományok kisebb háromszög-hármasokra való feldarabolásával keletkeznek. Ezzel ekvivalens meghatározásuk szerint a síkba rajzolható 3-fák.

A lekötött gráfok olyan gráfok, melyek minden periferikus köre háromszög. Egy maximális síkbarajzolható gráfban (és általánosabban, bármely poliédergráfban) a periferikus körök a tartományokkal egyeznek meg, tehát a maximális síkbarajzolható gráfok lekötöttek. A lekötött gráfok közé tartoznak a merev körű gráfok, és a lekötött gráfok pontosan azok a gráfok, melyek merev körű gráfokból és maximális síkgráfokból előállíthatók a klikk-összeg művelet segítségével.^[5]

Külsíkgráfok

A külsíkgráfok (outerplanar vagy outerplanáris gráfok) olyan gráfok, melyek beágyazhatók a síkba oly módon, hogy minden csúcsuk a beágyazás a külső, végtelen tartományához tartozzon. Minden külsíkgráf síkgráf, de a fordítottja nem igaz: a K₄ síkgráf, de nem külsíkgráf. A Kuratowski-tételhez hasonló tétel kimondja, hogy egy véges gráf akkor és csak akkor külsíkgráf, ha nem tartalmazza homeomorf részgráfként a K₄-et vagy a K_2,3-at.

Egy gráf 1-külsíkba rajzolása megegyezik a külsíkba rajzolásával. A k > 1 esetekben egy gráf síkba rajzolása akkor k-külsíkba rajzolás, ha a külső tartományhoz tartozó csúcsok eltávolításával egy (k − 1)-külsíkba rajzolás jön létre. Egy gráf akkor k-külsíkgráf, ha van neki k-külsíkba rajzolása.

Halin-gráfok

A Halin-gráfok irányítatlan, 2 fokszámú csúcsok nélküli fákból állíthatók elő a levelek körökbe csatolásával, a síkba ágyazás által meghatározott sorrendben. Ezzel ekvivalens meghatározásban olyan poliédergráfok, melyeknek egy kijelölt tartománya az összes többivel szomszédos. Minden Halin-gráf síkbarajzolható. A külsíkgráfokhoz hasonlóan a Halin-gráfok favastagsága is alacsony, ami miatt számos probléma könnyebben megoldható rajtuk, mint az általános síkgráfokon.^[6]

Egyéb kapcsolódó gráfcsaládok

Egy csúcsgráf (apex graph) olyan gráf, ami egyetlen csúcsának eltávolításával síkbarajzolhatóvá tehető; egy k-csúcsgráf legfeljebb k csúcs eltávolításával síkbarajzolhatóvá alakítható.

Egy 1-síkgráf olyan gráf, ami lerajzolható a síkba úgy, hogy minden élt legfeljebb egyszer messen egy másik; egy k-síkgráf olyan gráf, ami lerajzolható élenként legfeljebb k metszéssel. A többszörös metszést egyik esetben sem engedjük meg.

Egy térképgráf olyan gráf, amit a sík véges sok. egyszeresen összefüggő, belsejük tekintetétben diszjunkt régióiból lehet előállítani úgy, hogy a csúcsok a régiók, két csúcsot pedig akkor köt össze él, ha a hozzájuk tartozó régiók legalább egy határpontban találkoznak. Ha legfeljebb három régió találkozik egy pontban, a térképgráf síkba rajzolható, de ha négy vagy több régió találkozik, már nem feltétlenül.

Egy tóruszra rajzolható gráf olyan gráf, ami metsző élek nélkül beágyazható egy tóruszra. Általánosabban tekintve, egy gráf nemszáma (génusza) annak a minimális nemszámú kétdimenziós felületnek a nemszáma, melybe a gráf beágyazható; a síkbarajzolható gráfok génusza 0, síkba nem, de tóruszra rajzolható gráfok génusza 1.

A háromdimenziós térbe bármely gráf élmetszés nélkül beágyazható. Létezik azonban a síkba rajzolhatóság háromdimenziós analógiája, amit a láncmentesen beágyazható gráfok jelentenek, melyek úgy ágyazhatók a háromdimenziós térbe, hogy köreik összekapcsolódási száma 0 legyen (semelyik két köre se legyen topológiailag kapcsolódva). A síkgráfok Kuratowski-, illetve Wagner-féle jellemzéséhez hasonlóan, miszerint a síkbarajzolható gráfok nem tartalmazzák a K₅-öt és a K_3,3-at minorként, a láncmentesen beágyazható gráfok nem tartalmazzák a Petersen-gráfcsalád hét tagjának egyikét sem minorként. A külsíkgráfok, illetve síkbarajzolható gráfok azok a gráfok, melyek Colin de Verdière-gráfinvariánsa legfeljebb 2 vagy 3; a láncmentesen beágyazható gráfok invariánsa legfeljebb négy lehet.

Egy felfelé síkbarajzolható gráf olyan irányított körmentes gráf, mely lerajzolható úgy a síkba, hogy élei egymást nem metsző, felfelé irányítású görbék legyenek. Nem minden síkba rajzolható irányított körmentes gráf felfelé síkbarajzolható, és NP-teljes annak eldöntése, hogy adott gráf felfelé síkbarajzolható-e.

Síkbarajzolható gráfok leszámlálása

Az $n$ csúcsú, címkézett síkbarajzolható gráfok száma aszimptotikusan $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ , ahol $\gamma \approx 27,22687$ és $g\approx 0,43\times 10^{-5}$ .^[7]

Az $n$ csúcsú, címkézetlen, nem izomorf síkbarajzolható gráfok száma $27,2^{n}$ és $30,06^{n}$ között van.^[8]

Csaknem minden síkbarajzolható gráf exponenciális számú automorfizmussal rendelkezik.^[9]

További tények és definíciók

Minden síkbarajzolható gráf 4 részes, azaz színezhető legfeljebb négy színnel. Ezt a négyszín-tétel mondja ki.

A Fáry-tétel kimondja, hogy minden egyszerű síkbarajzolható gráf olyan módon is lerajzolható, hogy élei egymást nem metsző egyenes szakaszok legyenek. Egy univerzális ponthalmaz olyan pontok halmaza a síkban, hogy bármely n csúcsú gráfnak létezik olyan síkba ágyazása, ahol az összes csúcs a halmaz pontjainak valamelyikén van. Létezik a csúcsok számával négyzetesen arányos méretű univerzális ponthalmaz, egyszerűen az egész koordinátájú négyzetrácsot tekintve. Bármely egyszerű külsíkgráf, és így bármely fa is beágyazható a síkba úgy, hogy az összes csúcs egy körön legyen, az élek pedig a körlemezen belül lévő, egymást nem metsző egyenes szakaszok, ezért az n-csúcsú szabályos sokszögek az n csúcsú külsíkgráfok univerzális ponthalmazai. Kevésbé nyilvánvaló, de ez n általános helyzetű pontra is igaz.^[10]

Egy összefüggő, de nem feltétlenül egyszerű G gráf síkba rajzolásához tartozó G* duális gráf a következőképpen konstruálható: a G gráf minden tartománya (a korlátlant is beleértve) G* egy csúcsának felel meg, és G* csúcsait akkor kötjük össze, ha G-beli megfelelői szomszédosak voltak (ha több él mentén voltak szomszédosak, akkor többszörösen is). Így G*, mely maga is síkgráf, ugyanannyi éllel rendelkezik, mint G, ugyanannyi csúccsal, ahány tartománya volt G-nek és ugyanannyi tartománnyal, ahány csúcsa volt G-nek. A „duális” kifejezést az indokolja, hogy G** = G; itt az egyenlőség a gömbfelületbe ágyazás ekvivalenciájának a jele. Ha G egy konvex poliédernek megfelelő síkgráf, akkor G* a poliéder duálisának megfelelő síkgráf.

A duális gráfok azért is hasznosak, mert számos tulajdonságuk egyszerű módon kapcsolódik az eredeti gráf tulajdonságához, így egyes gráfokkal kapcsolatos eredmények bizonyíthatók úgy is, ha a gráfok duálisait vesszük alapul.

Bár a síkbaágyazható gráf egy konkrét beágyazásához tartozó duálisok egyediek (izomorfia erejéig), egy gráfnak létezhetnek különböző (nem izomorf) duálisai, melyek különböző (nem homeomorf) beágyazásaiból származnak.

Egy euklideszi gráf olyan gráf, melynek csúcsai a sík pontjainak felelnek meg, éleinek súlyozása pedig a pontok közötti euklideszi távolságnak; lásd geometriai gráfelmélet.

Egy síkgráf akkor konvex, ha minden tartományát (természetesen a végtelen tartományon kívül) konvex sokszögek határolják. Egy síkbarajzolható gráfnak pontosan akkor létezik konvex síkba rajzolása, ha egy 3-szorosan összefüggő síkgráf felosztásával előállítható.

A Scheinerman-sejtés (most már tétel) kimondja, hogy minden síkbarajzolható gráf előállítható a sík egyenes szakaszainak metszetgráfjaként.

A síkgráf-elválasztási tétel kimondja, hogy minden n-csúcsú síkbarajzolható gráf O(√n) csúcs eltávolításával két, legfeljebb 2n/3 méretű részgráfra particionálható. Ennek következménye, hogy a síkbarajzolható gráfok favastagsága és fafelbontásának szélessége szintén O(√n).

Két, v csúcsú síkbarajzolható gráfról O(v) időben eldönthető, hogy izomorfak-e vagy nem (lásd gráfizomorfizmus-probléma).^[11]

Egy síkbarajzolható gráf behálózottsági együtthatója (meshedness coefficient) normalizálja a korlátos tartományok számát (ami megegyezik a gráf ciklomatikus rangjával, a Mac Lane-féle síkgráfkritérium alapján) úgy, hogy elosztja 2n − 5-tel, tehát az n csúcsú síkgráfban lehetséges korlátos tartományok maximális számával. Így az együttható értéke 0 (fák) és 1 (maximális síkgráfok) között mozoghat.^[12]

Fordítás

Ez a szócikk részben vagy egészben a Planar graph 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

↑ Trudeau, Richard J.. Introduction to Graph Theory, Corrected, enlarged republication., New York: Dover Pub., 64. o. (1993). ISBN 978-0-486-67870-2. Hozzáférés ideje: 2012. augusztus 8. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.”
↑ Rajzoljuk le síkba a gráfot. Ekkor külön-külön mind a $k$ komponensre teljesül az Euler-formula. Mivel minden csúcs és minden él pontosan egy komponenshez tartozik, $v=\sum v_{i}$ és $e=\sum e_{i}$ , ahol $v_{i}$ és $e_{i}$ az $i$ -edik komponens csúcsainak, illetve éleinek száma. A „külső” tartományok azonban mindegyik komponensnél azonosak, ezért $f=\sum f_{i}-(k-1)$ . A komponensekre felírt Euler-formulából adódik az állítás.
↑ Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, DOI 10.1007/BF00353652.
↑ Bhasker, Jayaram & Sahni, Sartaj (1988), "A linear algorithm to find a rectangular dual of a planar triangulated graph", Algorithmica 3 (1–4): 247–278, DOI 10.1007/BF01762117.
↑ Seymour, P. D. & Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, DOI 10.1002/jgt.3190080206.
↑ Sysło, Maciej M. & Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 248–256, DOI 10.1007/BFb0071635.
↑ (2009) „Asymptotic enumeration and limit laws of planar graphs”. Journal of the American Mathematical Society 22, 309–329. o. DOI:10.1090/s0894-0347-08-00624-3.
↑ (2006) „Planar Graphs, via Well-Orderly Maps and Trees”. Graphs and Combinatorics 22, 185–202. o. DOI:10.1007/s00373-006-0647-2.
↑ „Random planar graphs”. Journal of Combinatorial Theory, Series B 93 (2), 187–205. o. DOI:10.1016/j.jctb.2004.09.007.
↑ (Gritzmann et al. 1991).
↑ I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.
↑ Buhl, J.; Gautrais, J. & Sole, R.V. et al. (2004), "Efficiency and robustness in ant networks of galleries", European Physical Journal B: Condensed Matter and Complex Systems (Springer-Verlag) 42 (1): 123–129, DOI 10.1140/epjb/e2004-00364-9.

Források

Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie", Fundamenta Mathematicae 15: 271–283, <http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf>.
Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen 114: 570–590, DOI 10.1007/BF01594196.
Boyer, John M. & Myrvold, Wendy J. (2005), "On the cutting edge: Simplified O(n) planarity by edge addition", Journal of Graph Algorithms and Applications 8 (3): 241–273, doi:10.7155/jgaa.00091, <http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf>.
McKay, Brendan & Brinkmann, Gunnar, A useful planar graph generator, <http://cs.anu.edu.au/~bdm/plantri/>.
de Fraysseix, H.; Ossona de Mendez, P. & Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science 17 (5): 1017–1029, DOI 10.1142/S0129054106004248. Special Issue on Graph Drawing.
D.A. Bader and S. Sreshta, A New Parallel Algorithm for Planarity Testing, UNM-ECE Technical Report 03-002, October 1, 2003.
Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B 24 (3): 374, DOI 10.1016/0095-8956(78)90059-X.
Gritzmann, P.; Mohar, B. & Pach, János et al. (1991), "Embedding a planar triangulation with vertices at specified positions", American Mathematical Monthly 98 (2): 165–166.

További információk

A Wikimédia Commons tartalmaz Síkbarajzolható gráf témájú médiaállományokat.

Edge Addition Planarity Algorithm Source Code, version 1.0 — Free C source code for reference implementation of Boyer–Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator. An open source project with free licensing provides the Edge Addition Planarity Algorithms, current version.
Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
Boost Graph Library tools for planar graphs, including linear time planarity testing, embedding, Kuratowski subgraph isolation, and straight-line drawing.
3 Utilities Puzzle and Planar Graphs
NetLogo Planarity model — NetLogo version of John Tantalo's game

Matematikaportál • összefoglaló, színes tartalomajánló lap

[1] Trudeau, Richard J.. Introduction to Graph Theory, Corrected, enlarged republication., New York: Dover Pub., 64. o. (1993). ISBN 978-0-486-67870-2. Hozzáférés ideje: 2012. augusztus 8. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.”

[2] Rajzoljuk le síkba a gráfot. Ekkor külön-külön mind a $k$ komponensre teljesül az Euler-formula. Mivel minden csúcs és minden él pontosan egy komponenshez tartozik, $v=\sum v_{i}$ és $e=\sum e_{i}$ , ahol $v_{i}$ és $e_{i}$ az $i$ -edik komponens csúcsainak, illetve éleinek száma. A „külső” tartományok azonban mindegyik komponensnél azonosak, ezért $f=\sum f_{i}-(k-1)$ . A komponensekre felírt Euler-formulából adódik az állítás.

[3] Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, DOI 10.1007/BF00353652.

[4] Bhasker, Jayaram & Sahni, Sartaj (1988), "A linear algorithm to find a rectangular dual of a planar triangulated graph", Algorithmica 3 (1–4): 247–278, DOI 10.1007/BF01762117.

[5] Seymour, P. D. & Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, DOI 10.1002/jgt.3190080206.

[6] Sysło, Maciej M. & Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 248–256, DOI 10.1007/BFb0071635.

[7] (2009) „Asymptotic enumeration and limit laws of planar graphs”. Journal of the American Mathematical Society 22, 309–329. o. DOI:10.1090/s0894-0347-08-00624-3.

[8] (2006) „Planar Graphs, via Well-Orderly Maps and Trees”. Graphs and Combinatorics 22, 185–202. o. DOI:10.1007/s00373-006-0647-2.

[9] „Random planar graphs”. Journal of Combinatorial Theory, Series B 93 (2), 187–205. o. DOI:10.1016/j.jctb.2004.09.007.

[10] (Gritzmann et al. 1991).

[11] I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.

[12] Buhl, J.; Gautrais, J. & Sole, R.V. et al. (2004), "Efficiency and robustness in ant networks of galleries", European Physical Journal B: Condensed Matter and Complex Systems (Springer-Verlag) 42 (1): 123–129, DOI 10.1140/epjb/e2004-00364-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]