Egy maximális külsíkgráf és 3-színezéseA K4teljes gráf a legkisebb síkgráf, ami nem outerplanáris
A matematika, azon belül a gráfelmélet területén egy külsíkgráf, outerplanáris vagy outerplanar gráf olyan síkba rajzolhatógráf, amely rendelkezik olyan síkba rajzolással, ahol az összes csúcs a rajzolás külső tartományába esik.
Az outerplanar gráfok nevüket az őket elsőként tanulmányozó (Chartrand & Harary 1967)-tól kapták. Chartrand és Harary egy alapgráf két kópiájának teljes párosítással való összekötésével (például az általánosított Petersen-gráfok egy része így állítható elő két egyforma körgráfból) kapott gráfok síkba rajzolhatósága eldöntésének problémáját tanulmányozva jutottak el az outerplanar gráfokhoz. Megmutatták, hogy ha az alapgráf kétszeresen összefüggő, az említett módon kapott gráf pontosan akkor síkgráf, ha az alapgráf külsíkgráf és a párosítás a külső körrel diéder-permutációt alkot.
Chartrand és Harary igazolták a Kuratowski-tétel analógját külsíkgráfokra, miszerint egy gráf akkor és csak akkor külsíkgráf, ha nem tartalmazza homeomorf részgráfként sem a K4, sem a K2,3 gráfot.
Meghatározás és karakterizáció
Egy külsíkgráf olyan irányítatlan gráf, amely metszésmentesenbeágyazható az euklideszi síkba oly módon, hogy az összes csúcs a rajzolás végtelen lapjához tartozzék. Más szóval, egyetlen csúcsot sem vesznek körül teljesen élek. Egy másik megfogalmazás szerint, egy G gráf akkor outerplanáris, ha a minden más csúcshoz éllel csatlakozó új csúcs hozzáadásával kapott G' gráf síkgráf.[1]
Egy maximális külsíkgráf olyan külsíkgráf, amelyhez nem lehetséges új éleket hozzáadni az outerplanaritás fenntartásával. Minden n csúcsú maximális külsíkgráfnak pontosan 2n − 3 éle van, és minden véges tartománya háromszög alakú.
Egy külsíkgráf akkor és csak akkor kétszeresen összefüggő, ha a külső tartománya egyszerű, azaz ismétlődés nélküli kört alkot. Egy külsíkgráf akkor és csak akkor hamiltoni, ha kétszeresen összefüggő; ebben az esetben a külső tartomány alkotja az egyetlen Hamilton-körét.[5] Általánosabban, a külsíkgráf leghosszabb körének nagysága megegyezik a legnagyobb kétszeresen összefüggő komponense csúcsainak számával. Az előbbi okokból a külsíkgráfok Hamilton-köreinek, illetve leghosszabb köreinek megkeresése lineáris időben megoldható feladat, míg általános gráfokra a probléma NP-teljes.
A maximális külsíkgráfok a hamiltoniságnál erősebb feltételnek is megfelelnek: csúcs-pánciklikusok (), tehát egy n csúcsú maximális külsíkgráf bármely v csúcsához és bármely 3≤k≤n számhoz tartozik v-t tartalmazó, k hosszúságú kör. Adott hosszúságú kör megkapható a gráfhoz egyetlen éllel kapcsolódó háromszögek ismétlődő eltávolításával (úgy, hogy az eltávolított csúcs ne a v legyen), amíg a maradék gráf külső tartománya éppen k méretű.[6]
Egy síkgráf pontosan akkor külsíkgráf, ha minden kétszeresen összefüggő komponense is külsíkgráf.[4]
Színezés
Minden hurokmentes külsíkgráf kiszínezhető legfeljebb három szín felhasználásával;[7] ez a tény nagy jelentőséget kap a Chvátal-féleművészeti galéria probléma egyszerűsített bizonyításában, amit (Fisk 1978) végzett el. A 3-színezés lineáris idő alatt megtalálható egy mohó színezési algoritmussal, ami eltávolít egy legfeljebb 2 fokszámú csúcsot, a maradék gráfot rekurzívan kiszínezi, majd az eltávolított csúcsot visszahelyezi a két szomszédjától eltérő színnel.
A Vizing-tétel szerint bármely gráf élkromatikus száma (az élek színezéséhez szükséges színek minimális száma, ha nem engedjük meg, hogy két szomszédos él azonos színű legyen) vagy a gráf maximális fokszáma, vagy a maximális fokszám plusz 1. A külsíkgráfok esetében azonban az élkromatikus szám csaknem mindig megegyezik a maximális fokszámmal, kivéve azt az esetet, amikor a gráf egy páratlan hosszúságú kört alkot.[8] Az optimális számú színnel történő élszínezés lineáris idejű algoritmussal megtalálható, a gyenge duális fa szélességi keresését alapul véve.[7]
Egyéb tulajdonságok
Az outerplanar gráfok degeneráltsága legfeljebb 2: minden részgráfja tartalmaz legfeljebb 2 fokszámú csúcsot.[9]
Az outerplanar gráfok favastagsága legfeljebb 2, amiből következik, hogy számos gráfoptimalizálási probléma, ami általános gráfok esetében NP-teljes, dinamikus programozás útján polinomiális időben megoldható a külsíkgráfokra. Általánosabban, a k-külsíkgráfok (lásd lentebb) favastagsága O(k).[10]
Minden külsíkgráf megadható a síkban tengelyükkel egymáshoz igazodó téglalapokmetszetgráfjaként, ezért a külsíkgráfok boxicity tulajdonsága legfeljebb 2.[11]
Kapcsolódó gráfcsaládok
Egy kaktuszgráf. A kaktuszforma a külsíkgráfok egy típusa.
Minden külsíkgráf egyben síkgráf is. Minden külsíkgráf egy soros-párhuzamos gráf részgráfja.[12] Azonban nem minden soros-párhuzamos síkgráf külsíkgráf.
A K2,3teljes páros gráf síkgráf és soros-párhuzamos, de nem külsíkgráf. A K4teljes gráf pedig síkgráf, de se nem soros-párhuzamos, sem pedig külsíkgráf.
Minden fa és kaktusz külsíkgráf.[13]
Egy beágyazott külsíkgráf gyenge duálisa (az a gráf, aminek minden csúcsa a beágyazás egy korlátos tartományának felel meg, élei pedig a szomszédos korlátos tartományoknak megfelelő csúcsok között húzódnak) erdő, egy Halin-gráf gyenge duálisa pedig külsíkgráf. Egy síkgráf akkor és csak akkor outerplanar, ha gyenge duálisa erdő, akkor és csak akkor Halin-gráf, ha gyenge duálisa kétszeresen összefüggő és outerplanar.[14]
Értelmezhető az outerplanaritás mértéke. Egy gráf 1-outerplanar beágyazása megegyezik a külsíkgráf-beágyazással. A k > 1 értékekre egy síkba rajzolás akkor k-outerplanar, ha a külső tartomány csúcsainak eltávolításával (k − 1)-outerplanar beágyazást kapunk.
Egy gráf akkor k-outerplanar vagy k-külsíkgráf, ha van k-outerplanar beágyazása.[15]
Egy outer-1-síkgráf vagy kül-1-síkgráf, az 1-síkgráfok analógiájára lerajzolható egy korongra úgy, hogy a csúcsok a határon legyenek és élenként legfeljebb egy metszés essen.
Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
Fleischner, Herbert J.; Geller, D. P. & Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society38: 215–219.
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.
Wessel, W. & Pöschel, R. (1985), "On circle graphs", in Sachs, Horst, Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, vol. 73, Teubner-Texte zur Mathematik, B.G. Teubner, pp. 207–210. As cited by (Unger 1988).
