Nouseva tasoesitys

Suunnatun asyklisen graafin  nouseva tasoesitys on graafin upotus euklidiseen avaruuteen , jossa reunat on esitetty ei-leikkaavina monotonisesti kasvavina käyrinä. Toisin sanoen mitä tahansa reunaa edustavalla käyrällä on oltava se ominaisuus, että mikä tahansa vaakaviiva leikkaa sen korkeintaan yhdessä pisteessä, ja kaksi reunaa ei voi leikkaamaan muita kuin päissä [1] [2] . Tässä mielessä se on ihanteellinen tapaus kerrokselliselle graafin piirtämiselle , graafin esitystyylille, jossa monotoniset käyrät voivat leikata, mutta jossa leikkauspisteiden määrä on minimaalinen.

Kuvaukset

Suunnatun asyklisen graafin on oltava tasomainen , jotta sillä olisi nouseva tasoesitys, mutta jokaisella tasomaisella asyklisellä graafilla ei ole tällaista esitystä. Kaikista tasomaisesti suunnatuista asyklisistä grafiikoista, joissa on yksi lähde (kärki, jolla ei ole sisään tulevia kaaria) ja nielu (piste, jolla ei ole lähteviä kaaria), graafit, joissa on nouseva tasoesitys, ovat st -tasograafit , tasograafit , joissa lähde ja nielu kuuluvat samaan ja samaan pintaan ainakin yhdelle tasograafin upotukselle. Yleisemmin graafilla G on nouseva tasoesitys silloin ja vain, jos se on suunnattu, asyklinen, ja se on st -tasograafin aligraafi samassa pistejoukossa [3] [4] [5] [6] .

Nousevassa sisäkkäisyydessä kuhunkin kärkeen saapuvien ja lähtevien kaarien joukko seuraavat peräkkäin kärjen kaarien syklisessä järjestyksessä . Tietyn suunnatun asyklisen graafin tasomaisen upotuksen sanotaan olevan bimodaalinen , jos sillä on tämä ominaisuus. Myös kahden peräkkäisen kaaren välinen kulma, joilla on sama suunta tietyssä kärjessä, voidaan merkitä pieneksi , jos se on pienempi kuin , tai suureksi , jos se on suurempi kuin . Jokaisella nielulla on oltava täsmälleen yksi suuri kulma, ja millään kärjellä, joka ei ole lähde tai nielu, ei saa olla suurta kulmaa. Lisäksi esityksen jokaisella sisäpinnalla on oltava kaksi pienempiä kulmaa enemmän kuin pääkulmia, ja ulkopinnalla on oltava kaksi pääkulmaa enemmän kuin pienet kulmat. Oikea tehtävä  on kulmien merkintä, joka täyttää kuvatut ominaisuudet. Kaikilla ylävirran liitteillä on kelvollinen tarkoitus. Sitä vastoin jokaisella suunnatulla asyklisellä graafilla, jossa on bimodaalinen tasoupotus oikealla osoituksella, on nouseva tasoesitys, joka voidaan rakentaa lineaarisessa ajassa [7] [8] [9] [10] .

Toinen kuvaus on mahdollista kaavioille, joissa on yksi lähde. Tässä tapauksessa ylöspäin suuntautuvan tasomaisen upotuksen on lähdettävä ulkopinnasta ja missä tahansa graafin suuntaamattomassa syklissä on oltava vähintään yksi kärki, johon syklin molemmat kaaret tulevat (esimerkiksi kuvan yläreunassa oleva kärkipiste ). Päinvastoin, jos upotuksella on molemmat nämä ominaisuudet, se vastaa ylävirran upottamista [11] [12] [13] .

Laskennallinen monimutkaisuus

Tiedetään, että jotkin erityistapaukset ylöspäin suuntautuvan tasoisuuden tarkistamiseksi voidaan tehdä polynomiajassa :

• Tarkistetaan, onko graafi st -tasoinen, voidaan tehdä lineaarisessa ajassa lisäämällä reuna s :stä t :hen ja tarkistamalla, onko jäljellä oleva graafi tasomainen. Samoja linjoja pitkin on mahdollista rakentaa nouseva tasoesitys (jos sellainen on) suunnatusta asyklisestä graafista yhdellä lähteellä ja uppoamalla lineaarisessa ajassa [14] [15] .
• Testaa , voidaanko kiinteällä tasomaisella injektiolla oleva suunnattu graafi piirtää nousevaksi tasomaiseksi yhteensopivalla injektiolla , voidaan tehdä tarkistamalla liitteen bimodaalinen ja mallintamalla yhteensopiva osoitusongelma verkkovirta - ongelmana . Ajoaika on lineaarinen tulograafin koossa ja polynomi lähteiden ja nielujen lukumäärässä [9] [10] [16] [17] [18] .
• Koska suunnatuissa polyhedraalisissa graafisissa kaavioissa on yksi tasomainen upotus, näiden graafien nousevan tasoesityksen olemassaolo voidaan varmistaa polynomiajassa [9] [10] [19] .
• Sen testaaminen, onko ulkotasolla suunnatulla asyklisellä graafilla nouseva tasoesitys, on myös polynomi [20] [21] [22] .
• Mikä tahansa rinnakkaissarjakuvaaja , joka on suunnattu rinnakkaissarjarakenteen mukaan, on nouseva tasomainen. Nouseva tasoesitys voidaan rakentaa suoraan graafin rinnakkais-sekvenssihajotelmasta [23] . Yleisemmin suuntaamattomien rinnakkaisten sarjamuotoisten graafien mielivaltaisen suuntauksen voidaan testata ylöspäin suuntautuvan tasomaisuuden suhteen polynomiajassa [24] .
• Mikä tahansa suuntautunut puu on nouseva taso [23] .
• Mikä tahansa kaksiosainen tasograafi, jonka reunat on suunnattu osasta toiseen, on nousevasti tasomainen [23] [25] .
• Monimutkaisempi polynomiaika-algoritmi tunnetaan nousevan tasomaisuuden tarkistamiseksi kaavioissa, joissa on yksi lähde mutta useita nieluja, tai päinvastoin [26] [27] [28] [29] .
• Nouseva tasoisuus voidaan tarkistaa polynomiajassa, jos kärkiosuuksien joukosta on vakiomäärä kolmikytkettyjä komponentteja ja tämä tarkistus on kiinteä-parametrisesti ratkaistava näissä kahdessa luvussa [30] [31] . Tarkistus on myös kiinteä-parametrisesti päätettävissä syötegraafin syklomaattisen luvun [31] suhteen .
• Jos kaikkien pisteiden y -koordinaatit ovat kiinteitä, niin x -koordinaatit, jotka tekevät esityksestä nousevan tasotason, löytyvät polynomiajassa [32] .

Ongelma sen määrittämisessä, onko monilähdettäisellä, monisink-tasosuuntaisella asyklisellä graafilla nouseva tasoesitys, on kuitenkin NP-täydellinen [33] [34] [35] .

Viivapiirros ja aluevaatimukset

Farin lause sanoo, että millä tahansa tasograafilla on esitys, jossa reunat esitetään viivasegmenteillä, ja sama pätee nousevaan tasograafiseen esitykseen - kaikilla nousevalla tasograafilla on nouseva tasograafinen esitys, jossa on kaaria janojen muodossa [36 ] [37] . Transitiivisesti pelkistetyn st -tasograafin suoraviivainen nouseva esitys voidaan saada käyttämällä hallitsevaa piirustustekniikkaa , jossa kaikilla pisteillä on kokonaislukukoordinaatit hilassa [38] [37] . Jotkut muut nousevat tasograafit saattavat kuitenkin vaatia eksponentiaalisen alueen kaikille suoraviivaisille nouseville tasoesityksilleen [36] [37] . Jos upotus on kiinteä, jopa suunnatut rinnakkaissarjakuvaajat ja suunnatut puut voivat vaatia eksponentiaalisen alueen [36] [39] [40] .

Hasse-kaaviot

Nousevat tasoesitykset ovat erityisen tärkeitä osittain järjestetyn joukkojen Hasse-kaavioissa , koska nämä kaaviot on yleensä piirrettävä nousevalla tyylillä. Graafiteorian kannalta tämä vastaa transitiivisesti pelkistettyjä suunnattuja asyklisiä graafia. Tällainen graafi voidaan muodostaa peittävästä osajärjestyssuhteesta, ja itse osajärjestys muodostaa graafissa saavutettavuusrelaation . Jos posetilla on yksi minimielementti, yksi maksimialkio ja nouseva tasoesitys, se muodostaa välttämättä hilan , joukon, jossa millä tahansa elementiparilla on yksi suurin alaraja ja yksi pienin yläraja [41] [ 42] . Hilan Hasse-kaavio on tasomainen silloin ja vain, jos sen järjestysmitta ei ylitä kahta [43] [44] . Kuitenkin joillakin dimensioiden kaksi osittaisilla järjestyksillä, joissa on minimi- ja maksimielementtejä, ei ole nousevaa tasoesitystä (otamme järjestyksen, jonka määrittää tilauksen transitiivisella sulkemisella ).

Muistiinpanot

1. ↑ Garg, Tamassia, 1995 .
2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 .
3. ↑ Garg, Tamassia, 1995 , s. 111–112.
4. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 172–179, §6.1 sisällyttäminen Planarst- kaavioon.
5. ↑ Di Battista, Tamassia, 1988 .
6. ↑ Kelly, 1987 .
7. ↑ Garg, Tamassia, 1995 , s. 112-115.
8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 180–188, §6.2 Kulmat ylöspäin suuntautuvissa piirustuksissa.
9. ↑ 1 2 3 Bertolazzi, Di Battista, 1991 .
10. ↑ 1 2 3 Bertolazzi, Di Battista, Liotta, Mannino, 1994 .
11. ↑ Garg, Tamassia, 1995 , s. 115.
12. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 209–210, §6.7.2 Kielletyt syklit yhden lähteen digrafeille.
13. ↑ Thomassen, 1989 .
14. ↑ Garg, Tamassia, 1995 , s. 119.
15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 179.
16. ↑ Garg, Tamassia, 1995 , s. 119–121.
17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 188–192, §6.3 Upward Planarity Testing of Embedded Digraphs.
18. ↑ Abbasi, Healy, Rextin, 2010 .
19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 191-192.
20. ↑ Garg, Tamassia, 1995 , s. 125–126.
21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 209, §6.7.1 Outerplanar Digraph.
22. ↑ Papakostas, 1995 .
23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , s. 212, §6.7.4 Jotkut ylöspäin suuntautuvien tasomaisten digrafien luokat.
24. ↑ Didimo, Giordano, Liotta, 2009 .
25. ↑ Di Battista, Liu, Kilpailija, 1990 .
26. ↑ Garg, Tamassia, 1995 , s. 122-125.
27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 195–200, §6.5 Yhden lähteen digrafien optimaalinen ylöspäin suuntautuva tasoisuustestaus.
28. ↑ Hutton, Lubiw, 1996 .
29. ↑ Bertolazzi, Di Battista, Mannino, Tamassia, 1998 .
30. ↑ Chan, 2004 .
31. ↑ 12 Healy , Lynch, 2006 .
32. ↑ Junger, Leipert, 1999 .
33. ↑ Garg, Tamassia, 1995 , s. 126-132.
34. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 201–209, §6.6 Ylöspäin suuntautuva tasoisuustestaus on NP-täydellinen.
35. ↑ Garg, Tamassia, 2001 .
36. ↑ 1 2 3 Di Battista, Frati, 2012 , s. 149–151, §5 Ylöspäin piirrokset.
37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 112–127 §4.7 Dominanssipiirrokset.
39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
40. ↑ Frati, 2008 .
41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 210–212 §6.7.3 Hilan kielletyt rakenteet.
42. ↑ Platt, 1976 .
43. ↑ Garg, Tamassia, 1995 , s. 118.
44. ↑ Baker, Fishburn, Roberts, 1972 .

Kirjallisuus

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Virtaus ja ylöspäin suuntautuva tasoisuus // Graafipiirustus: Algoritmit graafien visualisoimiseksi. - Prentice Hall , 1998. - S. 171-213. — ISBN 978-0-13-301615-4 .
• Giuseppe Di Battista, Fabrizio Frati. Piirustuspuut, ulkotasokuvaajat, sarja-rinnakkaiskuvaajat ja tasograafit pienellä alueella // Kolmekymmentä esseetä geometrisen graafin teoriasta. - Springer, 2012. - T. 29. - S. 121-165. — (Algoritmit ja kombinatoriaalit). — ISBN 9781461401100 . - doi : 10.1007/978-1-4614-0110-0_9 .
• Ashim Garg, Roberto Tamassia. Ylöspäin tasomaisuuden testaus // Järjestys . - 1995. - T. 12 , no. 2 . — S. 109–133 . - doi : 10.1007/BF01108622 .

• Sarmad Abbasi, Patrick Healy, Aimal Rextin. Upotetun ylöspäin suuntautuvan tasomaisuuden testauksen suoritusajan parantaminen // Information Processing Letters. - 2010. - T. 110 , no. 7 . — S. 274–278 . - doi : 10.1016/j.ipl.2010.02.004 .
• Baker KA, Fishburn PC, Roberts FS Dimension 2 osittaiset tilaukset  // Verkot. - 1972. - Osa 2 , no. 1 . — S. 11–28 . - doi : 10.1002/net.3230020103 .
• Paola Bertolazzi, Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Sarjan rinnakkaisen digraafin piirtäminen // International Journal of Computational Geometry & Applications. - 1994. - T. 4 , no. 4 . — S. 385–402 . - doi : 10.1142/S0218195994000215 .
• Paola Bertolazzi, Giuseppe Di Battista. Triconnected digraphs -testauksesta ylöspäin // Proceedings of the Seventh Annual Symposium on Computational Geometry (SCG '91, North Conway, New Hampshire, USA). - New York, NY, USA: ACM, 1991. - S. 272-280. - ISBN 0-89791-426-0 . doi : 10.1145 / 109648.109679 .
• Bertolazzi P., Di Battista G., Liotta G., Mannino C. Ylöspäin piirroksia kolmikytketyistä digrafeista // Algorithmica . - 1994. - T. 12 , no. 6 . — S. 476–497 . - doi : 10.1007/BF01188716 .
• Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia. Yhden lähteen digrafien optimaalinen ylöspäin suuntautuva tasoitestaus // SIAM Journal on Computing . - 1998. - T. 27 , no. 1 . — S. 132–169 . - doi : 10.1137/S0097539794279626 .
• Hubert Chan. Parametrisoitu algoritmi ylöspäin suuntautuvan tasomaisuuden testaamiseen // Proc. 12th European Symposium on Algorithms (ESA '04) . - Springer-Verlag, 2004. - T. 3221. - S. 157-168. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-540-30140-0_16 .
• Giuseppe Di Battista, Wei-Ping Liu, Ivan Rival. Kaksiosaiset kaaviot, ylöspäin suuntautuvat piirustukset ja tasoisuus // Tietojenkäsittelykirjeet . - 1990. - T. 36 , no. 6 . — S. 317–322 . - doi : 10.1016/0020-0190(90)90045-Y .
• Giuseppe Di Battista ja Roberto Tamassia. Asyklisten digrafien tasoesitysten algoritmit // Tietojenkäsittelyteoria . - 1988. - T. 61 , no. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
• Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Tasomaisten ylöspäin suuntautuvien piirustusten pinta-alavaatimus ja symmetrianäyttö // Diskreetti ja laskennallinen geometria . - 1992. - T. 7 , numero. 4 . — S. 381–401 . - doi : 10.1007/BF02187850 .
• Walter Didimo, Francesco Giordano, Giuseppe Liotta. Ylöspäin suuntautuvan spiraalin ja ylöspäin suuntautuvan tasomaisuuden testaus // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , no. 4 . - S. 1842-1899 . - doi : 10.1137/070696854 .
• Fabrizio Frati. Suunnattujen puiden ja muiden suunnattujen asyklisten kuvaajien perheiden tasomaiset piirustukset minimialueella // International Journal of Computational Geometry & Applications. - 2008. - T. 18 , no. 3 . — S. 251–271 . - doi : 10.1142/S021819590800260X .
• Ashim Garg, Roberto Tamassia. Ylöspäin suuntautuvan ja suoraviivaisen tasomaisuuden testauksen laskennallisesta monimutkaisuudesta // SIAM Journal on Computing . - 2001. - T. 31 , no. 2 . — S. 601–625 . - doi : 10.1137/S0097539794277123 .
• Patrick Healy, Karol Lynch. Kaksi kiinteän parametrin ohjattavaa algoritmia ylöspäin suuntautuvan tasomaisuuden testaamiseen // International Journal of Foundations of Computer Science. - 2006. - T. 17 , no. 5 . — S. 1095–1114 . - doi : 10.1142/S0129054106004285 .
• Michael D. Hutton, Anna Lubiw. Ylöspäin suuntautuva yhden lähteen asyklisten digrafien tasopiirustus // SIAM Journal on Computing . - 1996. - T. 25 , no. 2 . — S. 291–311 . - doi : 10.1137/S0097539792235906 . . Paperi esiteltiin ensimmäisen kerran 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
• Michael Junger, Sebastian Leipert. Tasomainen upotus lineaarisessa ajassa // Graph Drawing (Proc. GD '99) . - 1999. - T. 1731. - S. 72–81. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-66904-3 . - doi : 10.1007/3-540-46648-7_7 .
• David Kelly. Tasojärjestettyjen joukkojen perusteet // Diskreetti matematiikka . - 1987. - T. 63 , no. 2-3 . — S. 197–216 . - doi : 10.1016/0012-365X(87)90008-2 .
• Akhilleas Papakostas. Ulompitasoisten dagkien ylöspäin suuntautuva tasotestaus (laajennettu abstrakti) // Kaaviopiirros: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 10.–12. lokakuuta 1994, Proceedings. - Berliini: Springer, 1995. - T. 894. - S. 298-306. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/3-540-58950-3_385 .
• Platt CR Tasomaiset hilat ja tasograafit // Journal of Combinatorial Theory . - 1976. - T. 21 , no. 1 . - S. 30-39 . - doi : 10.1016/0095-8956(76)90024-1 . .
• Carsten Thomassen. Tasomaiset asykliset orientoidut graafit // Järjestys . - 1989. - V. 5 , no. 4 . - S. 349-361 . - doi : 10.1007/BF00353654 . .