Wikipédia

1-síkbarajzolható gráf

matematikai fogalom a gráfelméletben
Ez a közzétett változat, ellenőrizve: 2019. május 8.

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.

A Heawood-gráf lerajzolása 1-síkgráfként: az élek közül hatot egyetlen él metsz át, a maradék tizenöt él metszés nélküli.

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

szerkesztés

Az 1-síkbarajzolható gráfokat először (Ringel 1965) tanulmányozta, aki megmutatta, hogy legfeljebb hét szín szükséges a színezésükhöz.[1] Később sikerült pontosítani a szükséges színek számát, ami a legrosszabb esetben hatnak bizonyult.[2] 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.

 
A háromszög alapú hasáb gráfja csúcsainak és lapjainak színezéséhez hat színre van szükség

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ó.[2] 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ű.[3]

Élsűrűség

szerkesztés

Az n csúcsú 1-síkgráfok legfeljebb 4n − 8 éllel rendelkeznek.[4] 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.[5] 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.[6] 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.[7]

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.[8]

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.[9]

Teljes többrészes gráfok

szerkesztés
 
A K2,2,2,2 koktélpartigráf 1-síkbarajzolása

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ó.[7]

Számítási bonyolultság

szerkesztés

Adott gráf 1-síkbarajzolhatóságának tesztelése NP-teljes,[10][11] é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[12] vagy korlátozott sávszélességű gráfokról van szó.[13] 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ó.[13]

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.[14][15] Az viszont polinom időben eldönthető, hogy az 1-síkbarajzolás „kiegyenesíthető-e” ilyen módon.[16] 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ó.[17] Az 1-síkbaágyazható gráfok könyvvastagsága korlátos,[18] bár néhány 1-síkbarajzolható gráf, pl. a K2,2,2,2 könyvvastagsága legalább négy.[19]

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.[20]

Általánosítások és kapcsolódó fogalmak

szerkesztés

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.[21] Adott gráf SPQR-fájáról dinamikus programozással lineáris időben eldönthető, hogy kül-1-síkbarajzolható-e.[22][23] 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.[23]

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.[24]

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.[25] Az n csúcsú k-síkgráfok éleinek száma legfeljebb O(k1/2n),[26] favastagságuk pedig legfeljebb O((kn)1/2).[27] 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”) (wd) rendelkeznek.[28]

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

szerkesztés
  • Ez a szócikk részben vagy egészben az 1-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

szerkesztés
  1. ↑ Ringel, Gerhard (1965), "Ein Sechsfarbenproblem auf der Kugel", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 29: 107–117, DOI 10.1007/BF02996313.
  2. ↑ a b Borodin, O. V. (1984), "Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs", Metody Diskretnogo Analiza (no. 41): 12–26, 108.
  3. ↑ Albertson, Michael O. & Mohar, Bojan (2006), "Coloring vertices and faces of locally planar graphs", Graphs and Combinatorics 22 (3): 289–295, doi:10.1007/s00373-006-0653-4, <http://www.fmf.uni-lj.si/~mohar/Reprints/2006/BM06_GC22_Albertson_ColoringPlanarGraphs.pdf>.
  4. ↑ Schumacher, H. (1986), "Zur Struktur 1-planarer Graphen", Mathematische Nachrichten 125: 291–300.
  5. ↑ Czap, Július & Hudák, Dávid (2013), "On drawings and decompositions of 1-planar graphs", Electronic Journal of Combinatorics 20 (2): P54, <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p54>.
  6. ↑ Brandenburg, Franz Josef; Eppstein, David & Gleißner, Andreas et al. (2013), "On the density of maximal 1-planar graphs", in Didimo, Walter & Patrignani, Maurizio, Proc. 20th Int. Symp. Graph Drawing.
  7. ↑ a b Czap, Július & Hudák, Dávid (2012), "1-planarity of complete multipartite graphs", Discrete Applied Mathematics 160 (4-5): 505–512, DOI 10.1016/j.dam.2011.11.014.
  8. ↑ Suzuki, Yusuke (2010), "Re-embeddings of maximum 1-planar graphs", SIAM Journal on Discrete Mathematics 24 (4): 1527–1540, DOI 10.1137/090746835.
  9. ↑ Didimo, Walter (2013), "Density of straight-line 1-planar graph drawings", Information Processing Letters 113 (7): 236–240, DOI 10.1016/j.ipl.2013.01.013.
  10. ↑ Grigoriev, Alexander & Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica 49 (1): 1–11, DOI 10.1007/s00453-007-0010-x.
  11. ↑ Korzhik, Vladimir P. & Mohar, Bojan (2009), "Minimal obstructions for 1-immersions and hardness of 1-planarity testing", in Tollis, Ioannis G. & Patrignani, Maurizio, Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers, vol. 5417, Lecture Notes in Computer Science, Springer, pp. 302–312, DOI 10.1007/978-3-642-00219-9_29.
  12. ↑ Cabello, Sergio & Mohar, Bojan (2012), Adding one edge to planar graphs makes crossing number and 1-planarity hard. Expanded version of a paper from the 17th ACM Symposium on Computational Geometry, 2010.
  13. ↑ a b Bannister, Michael J.; Cabello, Sergio & Eppstein, David (2013), "Parameterized complexity of 1-planarity", Algorithms and Data Structures Symposium (WADS 2013).
  14. ↑ Eggleton, Roger B. (1986), "Rectilinear drawings of graphs", Utilitas Mathematica 29: 149–172.
  15. ↑ Thomassen, Carsten (1988), "Rectilinear drawings of graphs", Journal of Graph Theory 12 (3): 335–341, DOI 10.1002/jgt.3190120306.
  16. ↑ Hong, Seok-Hee; Eades, Peter & Liotta, Giuseppe et al. (2012), "Fáry's theorem for 1-planar graphs", in Gudmundsson, Joachim; Mestre, Julián & Viglas, Taso, Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012, Proceedings, vol. 7434, Lecture Notes in Computer Science, Springer, pp. 335–346, DOI 10.1007/978-3-642-32241-9_29.
  17. ↑ Alam, Md. Jawaherul; Brandenburg, Franz J. & Kobourov, Stephen G. (2013), "Straight-line grid drawings of 3-connected 1-planar graphs", Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, vol. 8242, Lecture Notes in Computer Science, pp. 83–94, doi:10.1007/978-3-319-03841-4_8, <http://www.cs.arizona.edu/~mjalam/straight_1_planar_3_connected.pdf>.
  18. ↑ Bekos, Michael A.; Bruckdorfer, Till & Kaufmann, Michael et al. (2015), "1-Planar graphs have constant book thickness", Algorithms – ESA 2015, vol. 9294, Lecture Notes in Computer Science, Springer, pp. 130–141, DOI 10.1007/978-3-662-48350-3_12.
  19. ↑ Bekos, Michael; Kaufmann, Michael & Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125.
  20. ↑ (Grigoriev & Bodlaender 2007). 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ó.
  21. ↑ Dehkordi, Hooman Reisi & Eades, Peter (2012), "Every outer-1-plane graph has a right angle crossing drawing", International Journal of Computational Geometry & Applications 22 (6): 543–557, DOI 10.1142/S021819591250015X.
  22. ↑ Hong, Seok-Hee; Eades, Peter & Katoh, Naoki et al. (2013), "A linear-time algorithm for testing outer-1-planarity", in Wismath, Stephen & Wolff, Alexander, 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, vol. 8242, Lecture Notes in Computer Science, pp. 71–82, DOI 10.1007/978-3-319-03841-4_7.
  23. ↑ a b Auer, Christopher; Bachmaier, Christian & Brandenburg, Franz J. et al. (2013), "Recognizing outer 1-planar graphs in linear time", in Wismath, Stephen & Wolff, Alexander, 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, vol. 8242, Lecture Notes in Computer Science, pp. 107–118, DOI 10.1007/978-3-319-03841-4_10.
  24. ↑ Chen, Zhi-Zhong; Grigni, Michelangelo & Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM 49 (2): 127–138, DOI 10.1145/506147.506148.
  25. ↑ Kainen, Paul (1973), "Thickness and coarseness of graphs", Abh. Math. Sem. Univ. Hamburg 39: 88–95, DOI 10.1007/BF02992822.
  26. ↑ Pach, János & Tóth, Géza (1997), "Graphs drawn with few crossings per edge", Combinatorica 17 (3): 427–439, DOI 10.1007/BF01215922.
  27. ↑ Dujmović, Vida; Eppstein, David & Wood, David R. (2015), "Genus, treewidth, and local crossing number", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 77–88.
  28. ↑ Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Springer, Theorem 14.4, p. 321, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.

Irodalom

szerkesztés
A lap eredeti címe: „https://hu.wiki.x.io/w/index.php?title=1-síkbarajzolható_gráf&oldid=21308193”