A matematika, azon belül a topologikus gráfelmélet területén egy 1-síkbarajzolható gráf, röviden 1-síkgráf (1-planar graph) olyan gráf, mely lerajzolható (beágyazható) az euklideszi síkba úgy, hogy a gráf minden élét legfeljebb egy másik éle metssze.

Az 1-síkbarajzolhatóság a síkba rajzolhatóság egyik legtermészetesebb, széles körben tanulmányozott általánosítása. Az 1-síkgráfok vizsgálata több mint fél évszázadra nyúlik vissza, miközben egyre növekvő figyelem irányul rá a gráfalgoritmusok, gráfrajzolás és számítási geometria területén.

Színezésük Az 1-síkbarajzolható gráfokat először tanulmányozta, aki megmutatta, hogy legfeljebb hét szín szükséges a színezésükhöz.. Később sikerült pontosítani a szükséges színek számát, ami a legrosszabb esetben hatnak bizonyult.. Arra, hogy a hat szín néha szükséges, a legegyszerűbb példa az 1-síkbarajzolható K6 teljes gráf. Annak bizonyítása azonban, hogy hat szín mindig elégséges is, jóval komplikáltabb.

Ringel eredeti célkitűzése a síkbarajzolható gráfok egy totális színezési problémájának megoldása volt, melyben a gráf csúcsainak és tartományainak színezése egyszerre történik oly módon, hogy semelyik szomszédos csúcs vagy tartomány nem lehet azonos színű. Nyolc szín nyilvánvalóan elegendő, hiszen ha az adott gráfra és duálisára külön-külön alkalmazzuk a négyszín-tételt, négy-négy diszjunkt színhalmaz elegendő a színezéshez. Kevesebb szín is elegendő lehet: tekintsük a segédgráfot, melynek csúcsai az adott síkgráf csúcsainak, valamint tartományainak felelnek meg, két csúcsot pedig akkor kötünk össze benne, ha az eredeti síkgráf szomszédos összetevőinek felelnek meg. Ekkor a segédgráf csúcsszínezése megfelel az eredeti gráf totális színezésének. A segédgráf 1-síkgráf, amiből következik, hogy Ringel csúcs-tartomány-színezési problémája hat színnel megoldható. A K6 teljes gráf nem alakulhat így ki segédgráfként, mégis, a totális színezési probléma megoldásához néha mind a hat színre szükség van; például ha a kiszínezendő síkgráf a háromszög alapú hasáb, akkor a 11 csúcs és lap hat színt igényel, mivel semelyik három nem lehet azonos színű..

Élsűrűség Az n csúcsú 1-síkgráfok legfeljebb 4n − 8 éllel rendelkeznek.. Ennél erősebb állítás, hogy az 1-síkbarajzolásnak legfeljebb n − 2 metszése lehet; a metsző élpárokból egyet-egyet eltávolítva síkgráfot kapunk, amiről ismert, hogy legfeljebb 3n − 6 éle van; ebből az 1-síkgráfok 4n − 8 élkorlátja közvetlenül következik.. A síkbarajzolható gráfoktól eltérően azonban (ahol adott csúcshalmaz maximális síkgráfjaiban ugyanannyi él található), léteznek olyan maximális 1-síkgráfok (melyekhez nem adható hozzá él az 1-síkbarajzolhatóság megszűnése nélkül), melyeknek a 4n − 8 élnél jóval kevesebbel rendelkeznek.. Az 1-síkgráf éleinek számára vonatkozó 4n − 8-as felső korlát segítségével meg is mutatható, hogy a K7 teljes gráf nem 1-síkgráf, hiszen 21 éle van, és ebben az esetben 4n − 8 = 20 < 21.

Egy 1-síkgráfot akkor nevezünk optimális 1-síkgráfnak, ha a maximálisan lehetséges 4n − 8 éllel rendelkezik. Egy optimális 1-síkgráf 1-síkbarajzolásakor a nem metsző élek a síkot szükségképpen négyszögelik (olyan poliédergráfot alkotnak, melyben minden tartomány négyszög alakú). A sík minden négyszögelése meghatároz egy optimális 1-síkgráfot, a négyszöglapokhoz két-két átló hozzáadásával. Következik az előzőekből, hogy minden optimális 1-síkgráf Euler-körű (minden csúcsának páros a fokszáma), a minimális fokszám 6, és legalább nyolc csúcs fokszáma pontosan 6. Ráadásul minden optimális 1-síkgráf 4-szeresen csúcsösszefüggő, és az ilyen gráf minden 4-csúcsú vágása a hozzá tartozó négyszögelés egy szeparátor köre..

Az egyenes szakaszokkal lerajzolható 1-síkgráfok éleire a kissé szorosabb 4n − 9 korlát vonatkozik, melyet végtelen sok gráf elér..

Teljes többrészes gráfok

Az 1-síkbarajzolható teljes gráfok, teljes páros gráfok és általánosabban a teljes többrészes gráfok teljes osztályozása ismeretes. Az összes K2,n alakú teljes páros gráf 1-síkbarajzolható, ahogy az összes K1,1,n alakú teljes háromrészes gráf is. Az előbbi példák végtelen halmazain kívül csak a következő teljes (többrészes) gráfok 1-síkbarajzolhatók: K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2 és ezek részgráfjai. A legkisebb, nem 1-síkbarajzolható teljes többrészes gráfok a K3,7, K4,5, K1,3,4, K2,3,3 és K1,1,1,1,3. Például a K3,6 teljes páros gráf 1-síkbarajzolható, mivel a K1,1,1,6 részgráfja, de a K3,7 nem 1-síkbarajzolható..

Számítási bonyolultság Adott gráf 1-síkbarajzolhatóságának tesztelése NP-teljes,.. és még akkor is NP-teljes marad, ha a gráfokat síkgráfokból egyetlen él hozzáadásával hozták létre. Expanded version of a paper from the 17th ACM Symposium on Computational Geometry, 2010. vagy korlátozott sávszélességű gráfokról van szó.. A probléma rögzített paraméter mellett kezelhető, ha a ciklikus rang vagy a fa mélysége a paraméterek, tehát ezen paraméterek korlátossága esetén polinom időben megoldható.

A síkgráfokra vonatkozó Fáry-tétellel szemben nem igaz valamennyi 1-síkbarajzolható gráfra, hogy egyenes szakaszokkal is 1-síkbarajzolhatók lennének... Az viszont polinom időben eldönthető, hogy az 1-síkbarajzolás „kiegyenesíthető-e” ilyen módon.. Továbbá, minden 3-szorosan csúcsösszefüggő 1-síkbarajzolható gráfnak létezik olyan 1-síkbarajzolása, melyben az egyenes szakaszokkal megrajzolható élek mellett legfeljebb egy élt kell törtvonallal megrajzolni, a lerajzolás külső tartományában. Ez a lerajzolás a gráf megadott 1-síkbarajzolásából lineáris időben előállítható.. Az 1-síkbaágyazható gráfok könyvvastagsága korlátos,. bár néhány 1-síkbarajzolható gráf, pl. a K2,2,2,2 könyvvastagsága legalább négy..

Az 1-síkbarajzolható gráfok lokális favastagsága (átmérő-favastagsága) korlátos, tehát létezik olyan (lineáris) f függvény, hogy a d átmérőjű 1-síkbarajzolható gráfok favastagsága legfeljebb f(d); ez a tulajdonság általánosabban igaz az összes olyan gráfra, ami egy korlátozott génuszú felületbe ágyazható élenként korlátos számú metszéssel. A síkgráfokhoz hasonlóan léteznek szeparátoraik, azaz olyan kisméretű csúcshalmazaik, melyek eltávolításával a gráf szétesik összefüggő komponensekre, melyek mérete az egész gráf konstans hányada. A fenti tulajdonságok alapján számos, eredetileg a síkbarajzolható gráfokra célzott algoritmus kiterjeszthető 1-síkbarajzolható gráfokra; ilyen a közelítő algoritmusok tervezésére szolgáló Baker-technika is. Például az említett módszerrel előállítható egy 1-síkbarajzolható gráf maximális elemszámú független halmazának polinomiális approximációs sémája.. Grigoriev és Bodlaender eredményében kizárólag ismert 1-síkbaágyazással rendelkező gráfok szerepelnek, az 1-síkbaágyazást úgy alakítják át síkbaágyazásra, hogy az élek metszéspontjait 4 fokszámú csúcsokká alakítják, majd fafelbontást alkalmaznak; módszerük azonban egyszerűen rámutat az eredeti 1-síkbarajzolható gráf korlátos helyi favastagságára, így a Baker-módszer közvetlenül, a beágyazás ismerete nélkül is alkalmazható.

Általánosítások és kapcsolódó fogalmak A külsíkgráfok 1-síkbarajzolási általánosítását outer-1-síkgráfnak vagy kül-1-síkgráfnak (outer-1-planar graphs). Ezek lerajzolhatók egy korongra úgy, hogy csúcsaik a határon legyenek és egy élre legfeljebb egy metszés essen. Ezek a gráfok minden esetben 1-síkbarajzolhatók úgy is, hogy az élek egyenes szakaszok legyenek, és csak derékszögben metszhetik egymást.. Adott gráf SPQR-fájáról dinamikus programozással lineáris időben eldönthető, hogy kül-1-síkbarajzolható-e... A gráf háromszorosan összefüggő komponensei (az SPQR-fa csúcsai) kizárólag körgráfokból, dipólusgráfokból és négy csúcsú teljes gráfokból állhatnak, amiből következik az is, hogy a kül-1-síkbarajzolható gráfok síkbarajzolhatók, favastagságuk pedig legfeljebb három. Az 1-síkgráfoktól eltérően a kül-1-síkgráfoknak létezik gráfminor-alapú karakterizációja: egy gráf pontosan akkor kül-1-síkgráf, ha nem szerepel benne az öt tiltott minor egyike sem.

Az 1-síkgráfok közé tartoznak a 4-térképgráfok, a sík régióinak szomszédsági viszonyaiból képzett gráfok, amennyiben bármely pontban legfeljebb négy régió találkozhat. A nem optimális 1-síkgráfok azonban nem feltétlenül térképgráfok..

Az 1-síkbarajzolható gráfok általánosításai a k-síkbarajzolható gráfok, melyekben a gráf minden éle lerajzoláskor legfeljebb k alkalommal van átmetszve (a 0-síkbarajzolható gráfok pontosan a síkbarajzolható gráfokkal egyeznek meg). Ringel meghatározása szerint G gráf lokális metszési száma (local crossing number) az a legkisebb k természetes szám, melyre G rendelkezik k-síkbarajzolással. Mivel a lokális metszési szám épp az optimális lerajzolás élei metszetgráfjának maximális fokszáma, a gráf vastagsága (a síkgráfok minimális száma, melyekbe az élek particionálhatók) pedig tekinthető a lerajzolás kromatikus számának, a Brooks-tételből következően a vastagság legfeljebb eggyel nagyobb a lokális metszési számnál.. Az n csúcsú k-síkgráfok éleinek száma legfeljebb O(k1/2n),. favastagságuk pedig legfeljebb O((kn)1/2).. Egy k-síkgráf korlátos mélységű minorja, melynek mélysége d, maga is (2d + 1)k-síkgráf, tehát az 1-síkgráfok és k-síkgráfok korlátos mélységű minorjai egyben ritka gráfok, amiből következően az 1-síkgráfok és k-síkgráfok ún. bounded expansionnel („korlátos kibővítéssel”) rendelkeznek..

A nem síkbarajzolható gráfok parametrizálhatók metszési számaik alapján is; ez a gráf lerajzolásaiban minimálisan fellépő metsző élpárok számát jelenti. Egy k metszési számú gráf k-síkbarajzolható, de visszafelé ez nem feltétlen igaz. Például a Heawood-gráf metszési száma 3, de a metszés nem feltétlenül ugyanazon az élen történik, ezért csak 1-síkbarajzolható, vagy akár úgy is lerajzolható, hogy egyidejűleg optimalizáljuk a gráfbeli metszések számát és az élenkénti metszések számát.

Kapcsolódó fogalom nem síkbarajzolható gráfokra még a gráf ferdesége, avagy a síkba rajzolhatóság eléréséhez minimálisan eltávolítandó élek száma.

Fordítás

Jegyzetek

Irodalom

Kategória:Síkgráfok