Kaavion upottaminen

Graafin upotus on topologisen graafiteorian puitteissa tutkittu graafin esitys tietyllä pinnalla , jossa pisteet liittyvät graafin kärkipisteisiin ja pinnalla olevat yksinkertaiset kaaret ( homeomorfiset kuvat [0,1]) graafin reunoihin . tavalla joka: $G$ $\Sigma$ $\Sigma$

kaavion reunaan liittyvän kaaren päätepisteet ovat pisteitä, jotka liittyvät kaavion kyseisen reunan päätepisteisiin $e$ $e$
mikään kaari ei sisällä pisteitä, jotka liittyvät muihin pisteisiin
kahta kaarta ei leikkaa näiden kaarien sisäpisteissä.

Tässä pinta on kompakti , yhdistetty 2 - jakotukki .

Epämuodollisesti graafin upottaminen pintaan on kuva graafista pinnalla siten, että sen reunat voivat leikata vain päätepisteissä. On hyvin tunnettua, että mikä tahansa äärellinen graafi voidaan upottaa kolmiulotteiseen euklidiseen avaruuteen [1] ja tasograafit voidaan upottaa kaksiulotteiseen euklidiseen avaruuteen . $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$

Usein upotus nähdään kuvatun kaltaisten esityksiä vastaavana luokkana (homeomorfismien mukaan). $\Sigma$

Graafisten visualisointiongelmien yhteydessä otetaan huomioon myös graafin upotuksen määritelmän heikko versio, jossa reunaleikkausten puuttumista ei vaadita. Näin ollen vahvaa määritelmää kuvataan "kuvaajan upotukseksi ilman leikkauskohtia" [2] .

Terminologia

Jos kuvaaja on upotettu suljettuun pintaan , graafin kärkipisteisiin ja reunoihin liittyvien pisteiden ja kaarien liiton komplementti on alueiden (tai pintojen) perheen perhe [3] . Kaksiulotteinen solun upottaminen tai kartta on upottaminen, jossa jokainen pinta on homeomorfinen avoimelle levylle [4] . Kaksiulotteinen suljetun solun upottaminen on upotus, jossa minkä tahansa pinnan sulkeminen on homeomorfinen suljetun levyn suhteen. $G$ $\Sigma$ $G$

Graafisten pinoamista käytetään usein sisäkkäisyyden synonyyminä, erityisesti tasokaavioiden tapauksessa.

Graafin suku on pienin kokonaisluku , jonka perusteella graafi voidaan upottaa suvun pintaan . Erityisesti tasograafilla on suku 0, koska se voidaan piirtää pallolle ilman itseleikkauksia. Graafin ei- orientoituva suku on pienin kokonaisluku , jolla graafi voidaan upottaa (ei-orientoituvan) suvun suuntaamattomaan pintaan [3] . $n$ $n$ $n$ $n$

Graafin Euler-suku on pienin kokonaisluku siten, että graafi voidaan upottaa (suuntautuvan) suvun suuntautuvaan pintaan tai (suuntautumattoman) suvun suuntaamattomaan pintaan . Graafi on yksinkertaisesti orientoitavissa , jos sen Euler-suku on pienempi kuin sen suuntautumaton. $n$ ${\tfrac {n}{2))$ $n$

Kuvaajan suurin suku on suurin kokonaisluku siten, että graafi voidaan upottaa litteäsoluiseksi (upotus on tasasoluinen, jos jokin suljettu käyrä, joka ei leikkaa graafin reunoja, supistuu yhteen pisteeseen) suuntautuvalle pinnalle suku . $n$ $n$

Kombinatorinen upottaminen

Sisäkkäinen graafi määrittelee yksiselitteisesti samaan kärkeen osuvien reunojen sykliset järjestykset . Kaikkien näiden syklisten järjestysten joukkoa kutsutaan ympyräjärjestelmäksi . Saman ympyränmuotoisen järjestelmän upotuksia pidetään vastaavina, ja vastaavaa upotusten ekvivalenssiluokkaa kutsutaan kombinatoriseksi upotukseksi (toisin kuin termi topologinen upottaminen , joka viittaa aiempaan pisteiden ja käyrien määritelmään). Joskus pyöreää järjestelmää kutsutaan "kombinatoriseksi upotukseksi" [5] [6] [7] .

Sisäkkäinen graafi määrittää myös luonnolliset sykliset reunajärjestykset, jotka määrittelevät sisäkkäisten pintojen rajat. Näillä fasettisuuntautuneilla järjestyksillä työskentely on kuitenkin vähemmän ilmeistä, koska joissakin tapauksissa jotkin reunat voidaan kulkea kahdesti kuljetettaessa kasvojen rajaa. Tämä pätee esimerkiksi aina, kun pesitetään puita, joissa on yksi reuna. Tämän kombinatorisen esteen voittamiseksi voidaan ajatella, että jokainen reuna on "jaettu" kahdeksi "puolireunaksi" tai "sivuksi". Näiden sopimusten mukaan raja kulkee kaikilla pinnoilla kunkin puolikkaan reunan läpi vain kerran, ja yhden reunan jokainen puolikas reuna kulkee aina vastakkaisiin suuntiin.

Laskennallinen monimutkaisuus

Graafin suvun määrittämisongelma on NP-täydellinen (ongelma sen määrittämisessä, onko graafilla, jolla on pisteet, on NP -täydellinen ) [8] . $n$ $g$

Samanaikaisesti graafin suvun määrittelyongelma on kiinteä-parametrisesti ratkaistava , eli tunnetaan polynomiaikaisia algoritmeja, joilla tarkistetaan, voidaanko graafi upottaa tietyn suvun pintaan. Sama pätee liitteen löytämiseen.

Ensimmäinen läpimurto tapahtui vuonna 1979 , kun aikamonimutkaisuusalgoritmeista raportoitiin itsenäisesti vuotuisessa ACM Symposium on Computational Theory - yksi ehdotti Ion Filotti ja Gary Miller ja toinen John Reif . Heidän lähestymistapansa olivat täysin erilaisia, mutta järjestelytoimikunnan ehdotuksesta he toimittivat yhdistetyn artikkelin [9] . $O(n^{O(g)})$

Vuonna 1999 osoitettiin, että kiinteän suvun tapaus voidaan ratkaista lineaarisessa ajassa graafisessa koossa ja kaksinkertaisessa eksponentiaalisessa ajassa suvussa [10] .

Kuvaajan upottaminen suurempien ulottuvuuksien tiloihin

Tiedetään, että mikä tahansa äärellinen graafi voidaan upottaa kolmiulotteiseen avaruuteen [1] .

Eräs tapa tällaiseen upotukseen on sijoittaa pisteitä (graafin kärkipisteitä) viivalle ja piirtää reunat käyrinä, jotka sijaitsevat erillisissä puolitasoissa , joilla tämä viiva on yhteinen raja kaikille puolitasoille. Tällaista upottamista kutsutaan kaaviokirjan upottamiseksi . Tämä metafora käy selväksi, jos kuvittelemme jokaisen puolitason kirjan sivuna. On selvää, että jotkin reunat voidaan piirtää ilman leikkauskohtia samalle "sivulle". Kuvaajan kirjan paksuus on kirjan upotuksen puolitasojen vähimmäismäärä.

Toisaalta mikä tahansa äärellinen graafi voidaan piirtää ilman leikkauspisteitä kolmiulotteisessa avaruudessa suorilla reunoilla asettamalla kärjet yleiseen asentoon siten, että mikään neljä ei ole samassa tasossa (eivät ole samassa tasossa). Tämä voidaan saavuttaa esimerkiksi sijoittamalla -:s kärki pisteeseen momenttikäyrällä . $i$ $(i,i^{2},i^{3})$

Kuvaajan upottamista kolmiulotteiseen avaruuteen, jossa kaksi sykliä ei ole topologisesti linkitetty, kutsutaan linkittämättömäksi upotukseksi . Graafilla on linkittämätön upotus silloin ja vain, jos se ei sisällä yhtään Peterson-perheen seitsemästä kaaviosta alaikäisenä .

Katso myös

Kaksoislinkitetty reunojen luettelo - tietorakenne tasoon upotetun graafin esittämiseen
Oikea kortti
Farin lause , jonka mukaan tasograafin tasossa on aina upotus, jossa kaikki kaaria edustavat janat.

Muistiinpanot

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

Kirjallisuus

Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey. Kaaviopiirros: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, 10.–12. lokakuuta 1994, Proceedings / Roberto Tamassia, Ioannis G. Tollis. - Springer, 1995. - T. 894. - S. 1-11. — ( Tietojenkäsittelytieteen luentomuistiinpanot ). - 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, Australia, 26.–28.7.2000, Proceedings. - Springer-Verlag, 2000. - T. 1858. - S. 95–104. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - 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, 10.–12. lokakuuta 1994, Proceedings . - Springer-Verlag, 1995. - T. 894. - S. 76-83. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/3-540-58950-3_358 .
Christian Duncan, Michael T. Goodrich, Stephen Kobourov. Tasopiirrokset korkeamman sukupolven kaavioista // Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, 22.-25.9.2009, Revised Papers . - Springer-Verlag, 2010. - T. 5849. - S. 45–56. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_7 .
Carsten Thomassen. Graafisukuongelma on NP-täydellinen // Journal of Algorithms. - 1989. - T. 10 , no. 4 . — S. 568–576 . - doi : 10.1016/0196-6774(89)90006-0 .
IS Filotti, Gary L. Miller, John Reif. Kaavion suvun määrittämisestä O(v O(g)) vaiheissa (Alustava raportti) // Proc. 11. Annu. ACM Symposium on Theory of Computing . - 1979. - S. 27-37. - doi : 10.1145/800135.804395 .
Bojan Mohar. Lineaarinen aikaalgoritmi kaavioiden upottamiseksi mielivaltaiseen pintaan // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , no. 1 . - S. 6-26 . - doi : 10.1137/S089548019529248X .
Jonathan Gross, Thomas W. Tucker. Topologinen graafiteoria . - Dover Publications, 2001. - ISBN 0-486-41741-7 .
A.K. Zvonkin, S.K. Lando. Graafit pinnoista ja niiden sovelluksista. - 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, 16.-19.7.2007, Proceedings. - Springer-Verlag, 2007. - T. 4598. - S. 243-253. — ( Tietojenkäsittelytieteen luentomuistiinpanot ). — ISBN 978-3-540-73544-1 . - doi : 10.1007/978-3-540-73545-8_25 .