Példagráfok Síkbarajzolható Síkba nem rajzolható Pillangógráf K5 Teljes gráf K4 Teljes gráf K3,3Há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.
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 -tel (az ötcsúcsú teljes gráffal) vagy -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 , sem a nem minora.
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 K5 és a K3,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íkbarajzolhatósá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 -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 , legfeljebb . Tehát , felhasználva az Euler-formulát, . Ezt az egyenlőtlenséget átrendezve adódik, hogy . 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 és az Euler-formula alkalmazásával, hogy .
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(v2)-nél. Tekintsük például a K3,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
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
.
Például a fenti pillangógráf esetében v = 5, e = 6 és f = 3. A K4 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 -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 é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:
.
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ű, összefüggő komponensből álló gráfokra a következőképpen módosul: , ahol a csúcsok, a tartományok, az élek számát jelöli.Rajzoljuk le síkba a gráfot. Ekkor külön-külön mind a komponensre teljesül az Euler-formula. Mivel minden csúcs és minden él pontosan egy komponenshez tartozik, és , ahol és az -edik komponens csúcsainak, illetve éleinek száma. A „külső” tartományok azonban mindegyik komponensnél azonosak, ezért . A komponensekre felírt Euler-formulából adódik az állítás.
Átlagos fokszám A és (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
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. vagy triangulated graph). 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..
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 K4 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 K4-et vagy a K2,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