Grafikonok beágyazása

A gráfbeágyazás egy gráf reprezentációja egy adott felületen , amelyet a topológiai gráfelmélet keretében vizsgálunk , ahol a pontokat gráfcsúcsokhoz , a felületen lévő egyszerű íveket ( homeomorf képek [0,1]) pedig gráfélekhez társítják. oly módon, hogy: $G$ $\Sigma$ $\Sigma$

a gráf éléhez tartozó ív végpontjai a gráf adott élének végpontjaihoz tartozó pontok $e$ $e$
egyetlen ív sem tartalmaz más csúcsokhoz kapcsolódó pontokat
nem metszi egymást két ív az ívek belső pontjain.

Itt a felület egy kompakt , összekapcsolt 2 - elosztó .

Informálisan egy gráf felületbe ágyazása a gráf felületen lévő képe oly módon, hogy élei csak a végpontokban metszik egymást. Köztudott, hogy háromdimenziós euklideszi térbe bármilyen véges gráf beágyazható [1] , kétdimenziós euklideszi térbe síkgráfok is beágyazhatók . $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$

A beágyazást gyakran a leírt típusú reprezentációk ekvivalencia osztályának tekintik (a homeomorfizmusok alapján ). $\Sigma$

A gráfvizualizációs problémák kontextusában a gráfbeágyazás definíciójának egy gyenge változatát is figyelembe vesszük, amelyben nem szükséges az élmetszéspontok hiánya. Ennek megfelelően az erős definíciót "a gráf metszéspontok nélküli beágyazása"-ként írják le [2] .

Terminológia

Ha a gráf egy zárt felületbe van beágyazva , akkor a gráf csúcsaihoz és éleihez tartozó pontok és ívek uniójának komplementere egy régiók (vagy lapok) családja [3] . A kétdimenziós cellabeágyazás vagy térkép olyan beágyazás, amelyben minden lap homeomorf egy nyitott lemezhez [4] . A kétdimenziós zárt cellás beágyazás olyan beágyazás, amelyben bármely felület lezárása egy zárt koronghoz képest homeomorf. $G$ $\Sigma$ $G$

A gráfhalmozást gyakran használják az egymásba ágyazás szinonimájaként, különösen síkbeli gráfok esetében.

A gráf nemzetsége az a legkisebb egész szám , amelyre a gráf beágyazható a nemzetség felületébe . Konkrétan egy síkgráfnak van 0 nemzetsége, mert önmetszéspontok nélkül rajzolható meg egy gömbön. A gráf nem orientálható nemzetsége a legkisebb egész szám , amelynél a gráf beágyazható egy (nem orientálható) genus irányítatlan felületébe [3] . $n$ $n$ $n$ $n$

A gráf Euler nemzetsége a legkisebb egész szám , amely lehetővé teszi, hogy a gráf beágyazható egy (orientálható) nemzetség orientálható felületébe vagy a (nem orientálható) nemzetség irányítatlan felületébe . Egy gráf egyszerűen orientálható , ha az Euler nemzetsége kisebb, mint a nem orientálható nemzetsége. $n$ ${\tfrac {n}{2))$ $n$

A gráf maximális nemzetsége az a maximális egész szám , amelynél a gráf síkcellás beágyazható (a beágyazás síkcellás, ha bármely zárt görbe, amely nem metszi a gráf éleit, összehúzódik egy ponttal) a gráf orientálható felületébe . nemzetség . $n$ $n$

Kombinatorikus beágyazás

A beágyazott gráf egyedileg határozza meg az ugyanahhoz a csúcshoz tartozó élek ciklikus sorrendjét . Mindezen ciklikus rendek halmazát körrendszernek [ nevezzük . Az azonos körrendszerű beágyazásokat ekvivalensnek tekintjük, a beágyazások megfelelő ekvivalenciaosztályát pedig kombinatorikus beágyazásnak nevezzük (szemben a topológiai beágyazás kifejezéssel, amely a pontok és görbék korábbi definíciójára utal). Néha magát a körrendszert "kombinatorikus beágyazásnak" nevezik [5] [6] [7] .

A beágyazott gráf természetes ciklikus élsorrendeket is meghatároz, amelyek meghatározzák az egymásba ágyazott lapok határait. Azonban ezekkel az oldal-orientált sorrendekkel kevésbé nyilvánvaló, mivel bizonyos esetekben előfordulhat, hogy egyes élek kétszer is áthaladnak egy lap határán. Ez például mindig igaz olyan fák beágyazásakor, amelyeknek egyetlen éle van. Ennek a kombinatorikus akadálynak a leküzdése érdekében minden élt úgy tekinthetünk, mintha két "félélre" vagy "oldalra" van osztva. Ezen konvenciók szerint minden lapon a határ csak egyszer halad át minden fél élen, és az egyik él minden féléle mindig ellentétes irányban.

Számítási összetettség

A gráf nemzetségének meghatározásának problémája NP-teljes (az a probléma, hogy egy csúcsokkal rendelkező gráfnak van-e genusa , NP-teljes ) [8] . $n$ $g$

Ugyanakkor a gráf nemzetség meghatározásának problémája fix-parametrikusan megoldható , vagyis ismertek olyan polinomiális idejű algoritmusok, amelyek ellenőrzik, hogy egy gráf beágyazható-e egy adott genusú felületbe. Ugyanez igaz a kötődés megtalálására is.

Az első áttörést 1979 -ben érte el, amikor az éves ACM Számításelméleti Szimpóziumon egymástól függetlenül jelentették be az időbonyolítási algoritmusokat – az egyiket Ion Filotti és Gary Miller , a másikat pedig John Reif javasolta . Megközelítésük teljesen eltérő volt, de a szervezőbizottság javaslatára összevont cikket nyújtottak be [9] . $O(n^{O(g)})$

1999 - ben kimutatták, hogy a fix genus esete lineáris időben megoldható gráfméretben és kétszeres exponenciális időben a genusban [10] .

Grafikon beágyazása nagyobb dimenziójú terekbe

Ismeretes, hogy bármely véges gráf beágyazható egy háromdimenziós térbe [1] .

Egy ilyen beágyazási módszer az, hogy pontokat (gráfcsúcsokat) helyezünk el egy egyenesen, és az éleket olyan különálló félsíkban lévő görbékként rajzoljuk meg , amelyeknek ez az egyenes az összes félsíkra közös határa. Az ilyen beágyazást grafikonkönyv -beágyazásnak nevezik . Ez a metafora világossá válik, ha minden félsíkot egy könyv lapjaként képzelünk el. Nyilvánvaló, hogy egyes élek metszéspontok nélkül is megrajzolhatók ugyanazon az "oldalon". A gráf könyvvastagsága a könyvbeágyazásban lévő félsíkok minimális száma.

Másrészt bármely véges gráf megrajzolható metszéspontok nélkül háromdimenziós térben, egyenes élekkel, ha a csúcsokat olyan általános helyzetbe helyezzük , hogy ne legyen egy síkban négy (nem egy síkban). Ezt például úgy érhetjük el, hogy a -edik csúcsot a nyomatékgörbe egy pontjára helyezzük . $én$ $(i,i^{2},i^{3})$

Egy gráf olyan háromdimenziós térbe történő beágyazását, amelyben nincs topológiailag két ciklus, kapcsolat nélküli beágyazásnak nevezzük . Egy gráfnak akkor és csak akkor van csatolatlan beágyazása, ha nem tartalmazza a Peterson család hét gráfjának egyikét sem .

Lásd még

Duplán linkelt éllista – adatstruktúra síkba ágyazott gráf ábrázolására
Korrekt kártya
Fari tétele , amely kimondja, hogy a síkgráf síkjába mindig van beágyazás, amelyben az összes ívet szakaszok ábrázolják.

Jegyzetek

↑ 1 2 Cohen, Eades, Lin, Ruskey, 1995 , p. 1–11.
↑ Katoh, Tanigawa, 2007 , p. 243–253.
↑ 12 Gross , Tucker, 2001 .
↑ Zvonkin, Lando, 2010 .
↑ Mutzel, Weiskircher, 2000 , p. 95–104.
↑ Didjev, 1995 , p. 76–83.
↑ Duncan, Goodrich, Kobourov, 2010 , p. 45–56.
↑ Thomassen, 1989 , p. 568–576.
↑ Filotti, Miller, Reif, 1979 , p. 27–37.
↑ Mohar, 1999 , p. 6–26.

Irodalom

Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey. Grafikonrajz: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, 1994. október 10–12., Proceedings / Roberto Tamassia, Ioannis G. Tollis. - Springer, 1995. - T. 894. - S. 1-11. — ( Számítástechnikai előadásjegyzetek ). - doi : 10.1007/3-540-58950-3_351 .
Petra Mutzel, René Weiskircher. Computing Optimal Embeddings for Planar Graphs // Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Ausztrália, 2000. július 26–28., Proceedings. - Springer-Verlag, 2000. - T. 1858. - S. 95–104. — (Számítástechnikai előadásjegyzetek). - ISBN 978-3-540-67787-1 . - doi : 10.1007/3-540-44968-X_10 .
Christo N. Didjev. Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 1994. október 10–12., Proceedings . - Springer-Verlag, 1995. - T. 894. - S. 76–83. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-58950-3_358 .
Christian Duncan, Michael T. Goodrich, Stephen Kobourov. Higher-Genus Graphs Planar Drawings // Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, 2009. szeptember 22-25., Revised Papers . - Springer-Verlag, 2010. - T. 5849. - S. 45-56. — (Számítástechnikai előadásjegyzetek). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_7 .
Carsten Thomassen. A gráf nemzetség probléma NP-teljes // Journal of Algorithms. - 1989. - T. 10 , sz. 4 . – S. 568–576 . - doi : 10.1016/0196-6774(89)90006-0 .
IS Filotti, Gary L. Miller, John Reif. A gráf nemzetségének meghatározásáról O(v O(g)) lépésekben (Előzetes jelentés) // Proc. 11. Annu. ACM Számítástechnikai Szimpózium . - 1979. - S. 27-37. - doi : 10.1145/800135.804395 .
Bojan Mohar. Lineáris idő algoritmus gráfok tetszőleges felületbe való beágyazásához // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , sz. 1 . – S. 6–26 . - doi : 10.1137/S089548019529248X .
Jonathan Gross, Thomas W. Tucker. Topológiai gráfelmélet . - Dover Publications, 2001. - ISBN 0-486-41741-7 .
A. K. Zvonkin, S. K. Lando. Grafikonok felületekről és alkalmazásaikról. - M. : MTSNMO, 2010. - ISBN 978-5-94057-588-7 .
Naoki Katoh, Shin-ichi Tanigawa. Enumerating Constrained Non-crossing Geometric Spanning Trees // Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Kanada, 2007. július 16-19., Proceedings. - Springer-Verlag, 2007. - T. 4598. - S. 243-253. — ( Számítástechnikai előadásjegyzetek ). — ISBN 978-3-540-73544-1 . - doi : 10.1007/978-3-540-73545-8_25 .