Növekvő síkbeli ábrázolás

Egy irányított aciklikus gráf növekvő síkbeli ábrázolása a  gráf beágyazása az euklideszi térbe , amelyben az élek nem metsző , monoton növekvő görbékként vannak ábrázolva . Azaz egy tetszőleges élt ábrázoló görbének olyan tulajdonsággal kell rendelkeznie, hogy bármely vízszintes egyenes legfeljebb egy pontban metszi azt, és két él nem metszi egymást, kivéve a végeit [1] [2] . Ebben az értelemben ideális eset a réteges gráfrajzhoz , egy olyan gráfábrázolási stílushoz, amelyben a monoton görbék metszhetik egymást, de a metszéspontok száma minimális.

Leírások

Egy irányított aciklikus gráfnak síknak kell lennie ahhoz, hogy növekvő síkbeli ábrázolása legyen, de nem minden síkbeli aciklikus gráf rendelkezik ilyen ábrázolással. Az összes síkbeli irányított aciklikus gráfok között, amelyek egyetlen forrással (egy csúcs, amelynek nincs bejövő íve) és egy nyelővel (olyan csúcs, amelynek nincs kimenő íve) között a növekvő síkbeli ábrázolású gráfok az st - planar gráfok , síkgráfok, amelyekben a forrás és a nyelő legalább egy síkgráf beágyazásnál ugyanahhoz és ugyanahhoz az oldalhoz tartozik. Általánosabban fogalmazva, egy G gráf akkor és csak akkor rendelkezik növekvő síkbeli ábrázolással, ha irányított, aciklikus, és egy st -sík gráf részgráfja ugyanazon a csúcshalmazon [3] [4] [5] [6] .

Növekvő egymásba ágyazáskor az egyes csúcsokra eső bejövő és kimenő ívek halmaza egymás után következik a csúcson lévő ívek ciklikus sorrendjében . Egy adott irányított aciklikus gráf síkbeli beágyazását bimodálisnak mondjuk, ha rendelkezik ezzel a tulajdonsággal. Ezenkívül egy adott csúcson két egymást követő, azonos orientációjú ív közötti szög kicsinek nevezhető, ha kisebb, mint , vagy nagynak , ha nagyobb, mint . Minden nyelőnek pontosan egy nagy szögűnek kell lennie, és minden olyan csúcsnak, amely nem forrás és nem nyelő, nem lehet nagy szöge. Ezen túlmenően az ábrázolás minden belső oldalának kettővel több kisebb szöget kell tartalmaznia, mint a főszögeket, a külső felületnek pedig kettővel több főszöget kell tartalmaznia, mint a kisszögeket. A helyes hozzárendelés  a sarkok jelölése, amely kielégíti a leírt tulajdonságokat. Minden upstream mellékletnek érvényes célja van. Ezzel szemben minden irányított aciklikus gráf, amely bimodális síkbeli beágyazással rendelkezik a megfelelő hozzárendeléssel, rendelkezik egy növekvő síkbeli ábrázolással, amely lineáris időben felépíthető [7] [8] [9] [10] .

Egy másik leírás is lehetséges az egyetlen forrású grafikonokhoz. Ebben az esetben a felfelé síkbeli beágyazásnak a külső felületről kell kiindulnia, és a gráf bármely irányítatlan ciklusának legalább egy olyan csúcsával kell rendelkeznie, amelybe a ciklus mindkét íve bejön (például az ábra legtetején lévő csúcs ). Ezzel szemben, ha egy beágyazás mindkét tulajdonsággal rendelkezik, akkor az egyenértékű egy upstream beágyazással [11] [12] [13] .

Számítási összetettség

Ismeretes, hogy néhány speciális eset a felfelé irányuló síkság ellenőrzésére polinomiális időben is elvégezhető :

• Annak ellenőrzése, hogy egy gráf st -síkú-e, megtehető lineáris időben , ha s -től t -hez adunk egy élt, és ellenőrizzük, hogy a fennmaradó gráf sík-e. Ugyanezen elvek mentén lehetséges egy irányított aciklikus gráf növekvő síkbeli ábrázolása (ha létezik) egyetlen forrással és lineáris időben süllyedővel [14] [15] .
• Annak tesztelése, hogy egy fix síkbeli injektálású irányított gráf rajzolható-e növekvő síkként kompatibilis injektálással, úgy végezhető el, ha ellenőrizzük, hogy a csatolás bimodális-e, és a kompatibilis hozzárendelési problémát hálózati áramlási problémaként modellezzük . A futási idő a bemeneti gráf méretében lineáris, a források és nyelők számában pedig polinom [9] [10] [16] [17] [18] .
• Mivel az irányított poliéder gráfok egyetlen síkbeágyazással rendelkeznek, ezeknek a gráfoknak a növekvő síkbeli ábrázolása polinomiális időben ellenőrizhető [9] [10] [19] .
• Annak tesztelése, hogy egy külső síkbeli irányított aciklikus gráfnak van- e növekvő síkbeli reprezentációja, szintén polinomiális [20] [21] [22] .
• Bármely párhuzamos-soros gráf , amely a párhuzamos-soros struktúra szerint orientált, növekvő síkbeli. Egy gráf párhuzamos-szekvenciális dekompozíciójából közvetlenül felépíthető növekvő síkbeli ábrázolás [23] . Általánosabban, irányítatlan párhuzamos soros gráfok tetszőleges orientációja tesztelhető polinomidőben felfelé irányuló síkosság szempontjából [24] .
• Bármely orientált fa növekvő síkbeli [23] .
• Bármely kétrészes síkgráf, amelynek élei egyik részről a másikra orientálódnak, növekvő síkbeli [23] [25] .
• Egy bonyolultabb polinomiális idő algoritmus ismert az egyetlen forrású, de több nyelővel rendelkező gráfok növekvő síkbeliségének ellenőrzésére, vagy fordítva [26] [27] [28] [29] .
• A növekvő síkság akkor ellenőrizhető polinomiális időben, ha a csúcsszakaszok között állandó számú hármas összefüggő komponens van, és ez az ellenőrzés fix-parametrikusan feloldható ebben a két számban [30] [31] . Az ellenőrzés a bemeneti gráf ciklomatikus számát tekintve is fix-parametrikusan eldönthető [31] .
• Ha az összes csúcs y -koordinátája rögzített, akkor az ábrázolást növekvő síkúvá tevő x -koordináták polinomidőben megtalálhatók [32] .

Azonban annak meghatározása, hogy egy többforrású, többnyelős síkbeli irányított aciklikus gráfnak van-e növekvő síkbeli reprezentációja, NP-teljes [33] [34] [35] .

Vonalrajz és területkövetelmények

Fari tétele kimondja, hogy minden síkgráfnak van olyan ábrázolása, amelyben az éleket vonalszakaszok ábrázolják, és ugyanez igaz a növekvő síkbeli ábrázolásra is – minden növekvő síkgráfnak van egy emelkedő síkbeli ábrázolása ívekkel szakaszok formájában [36 ] [37] . Egy tranzitívan redukált st -sík gráf egyenes vonalú növekvő ábrázolása a domináns rajzolási technikával állítható elő úgy , hogy minden csúcsnak egész koordinátája van a rácsban [38] [37] . Néhány más növekvő síkgráfhoz azonban szükség lehet exponenciális területre az összes egyenes vonalú növekvő síkbeli ábrázoláshoz [36] [37] . Ha a beágyazás rögzített, még az irányított párhuzamos soros gráfok és irányított fák is exponenciális területet igényelhetnek [36] [39] [40] .

Hasse diagramok

A növekvő síkbeli ábrázolások különösen fontosak a részben rendezett halmazok Hasse-diagramjainál , mivel ezeket a diagramokat általában növekvő stílusban kell megrajzolni. Gráfelmélet szempontjából ez tranzitívan redukált irányított aciklikus gráfoknak felel meg. Egy ilyen gráf egy lefedő részrendi relációból alakítható ki, és maga a részleges sorrend alkot elérhetőségi relációt a gráfban. Ha egy póznak van egy minimális eleme, egy maximális eleme, és van egy növekvő síkbeli ábrázolása, akkor szükségszerűen egy rácsot alkot , egy olyan halmazt, amelyben bármely elempárnak egyetlen legnagyobb alsó korlátja és egyetlen legkisebb felső korlátja van [41] [ 42] . Egy rács Hasse-diagramja akkor és csak akkor sík, ha annak ordinális mérete nem haladja meg a kettőt [43] [44] . Néhány minimális és maximum elemű kettes dimenziós részleges sorrend azonban nem rendelkezik növekvő síkbeli ábrázolással (a sorrend tranzitív lezárásával meghatározott sorrendet vesszük ).

Jegyzetek

1. ↑ Garg, Tamassia, 1995 .
2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 .
3. ↑ Garg, Tamassia, 1995 , p. 111–112.
4. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 172–179., 6.1. § Beépítés egy Planarst - grafikonba.
5. ↑ Di Battista, Tamassia, 1988 .
6. ↑ Kelly, 1987 .
7. ↑ Garg, Tamassia, 1995 , p. 112–115.
8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 180–188, §6.2 Szögek felfelé mutató rajzokban.
9. ↑ 1 2 3 Bertolazzi, Di Battista, 1991 .
10. ↑ 1 2 3 Bertolazzi, Di Battista, Liotta, Mannino, 1994 .
11. ↑ Garg, Tamassia, 1995 , p. 115.
12. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209–210, §6.7.2 Tiltott ciklusok egyforrású digráfokhoz.
13. ↑ Thomassen, 1989 .
14. ↑ Garg, Tamassia, 1995 , p. 119.
15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 179.
16. ↑ Garg, Tamassia, 1995 , p. 119–121.
17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 188–192, §6.3. Beágyazott digráfok felfelé irányuló síkossági vizsgálata.
18. ↑ Abbasi, Healy, Rextin, 2010 .
19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 191–192.
20. ↑ Garg, Tamassia, 1995 , p. 125–126.
21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209, §6.7.1 Külső síkbeli digráf.
22. ↑ Papakostas, 1995 .
23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , p. 212, §6.7.4 A felfelé irányuló síkbeli digráfok néhány osztálya.
24. ↑ Didimo, Giordano, Liotta, 2009 .
25. ↑ Di Battista, Liu, Rivális, 1990 .
26. ↑ Garg, Tamassia, 1995 , p. 122–125.
27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 195–200, §6.5 Egyforrású digráfok optimális felfelé irányuló síkossági vizsgálata.
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 , p. 126–132.
34. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 201–209, §6.6 A felfelé irányuló síkosság tesztelése NP-teljes.
35. ↑ Garg, Tamassia, 2001 .
36. ↑ 1 2 3 Di Battista, Frati, 2012 , p. 149–151, 5. § Felfelé mutató rajzok.
37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 112–127. §4.7 Dominanciarajzok.
39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
40. ↑ Frati, 2008 .
41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 210–212. §6.7.3 Tiltott szerkezetek a rácshoz.
42. ↑ Platt, 1976 .
43. ↑ Garg, Tamassia, 1995 , p. 118.
44. ↑ Baker, Fishburn, Roberts, 1972 .

Irodalom

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Flow and Upward Planarity // Grafikonrajz: Algoritmusok a grafikonok megjelenítéséhez. - Prentice Hall , 1998. - S. 171-213. — ISBN 978-0-13-301615-4 .
• Giuseppe Di Battista, Fabrizio Frati. Rajzfák, külső síkbeli gráfok, sorozatpárhuzamos gráfok és síkgráfok kis területen // Thirty Essays on Geometric Graph Theory. - Springer, 2012. - T. 29. - S. 121-165. — (Algoritmusok és kombinatorikusok). — ISBN 9781461401100 . - doi : 10.1007/978-1-4614-0110-0_9 .
• Ashim Garg, Roberto Tamassia. Felfelé irányuló síkosság vizsgálata // Rend . - 1995. - T. 12 , sz. 2 . – S. 109–133 . - doi : 10.1007/BF01108622 .

• Sarmad Abbasi, Patrick Healy, Aimal Rextin. A beágyazott felfelé irányuló síkosság-teszt futási idejének javítása // Information Processing Letters. - 2010. - T. 110 , sz. 7 . – S. 274–278 . - doi : 10.1016/j.ipl.2010.02.004 .
• Baker KA, Fishburn PC, Roberts FS Partial orders of dimension 2  // Networks. - 1972. - 2. évf . 1 . – S. 11–28 . - doi : 10.1002/net.3230020103 .
• Paola Bertolazzi, Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Sorozatpárhuzamos digráf rajzolása // International Journal of Computational Geometry & Applications. - 1994. - T. 4 , sz. 4 . – S. 385–402 . - doi : 10.1142/S0218195994000215 .
• Paola Bertolazzi, Giuseppe Di Battista. A háromkapcsolt digráfok felfelé ívelő teszteléséről // 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. Felfelé irányuló rajzok háromösszefüggő digráfokról // Algorithmica . - 1994. - T. 12 , sz. 6 . – S. 476–497 . - doi : 10.1007/BF01188716 .
• Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia. Egyforrású digráfok optimális felfelé irányuló síkossági tesztelése // SIAM Journal on Computing . - 1998. - T. 27 , sz. 1 . – S. 132–169 . - doi : 10.1137/S0097539794279626 .
• Hubert Chan. Paraméterezett algoritmus felfelé irányuló síkosság teszteléséhez // Proc. 12. Európai Algoritmus-szimpózium (ESA '04) . - Springer-Verlag, 2004. - T. 3221. - S. 157-168. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-540-30140-0_16 .
• Giuseppe Di Battista, Wei-Ping Liu, Ivan Rival. Kétrészes grafikonok, felfelé mutató rajzok és síkság // Information Processing Letters . - 1990. - T. 36 , sz. 6 . – S. 317–322 . - doi : 10.1016/0020-0190(90)90045-Y .
• Giuseppe Di Battista, Roberto Tamassia. Algoritmusok aciklikus digráfok síkbeli ábrázolásához // Elméleti számítástechnika . - 1988. - T. 61 , sz. 2-3 . – S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
• Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Területigény és síkbeli felfelé irányuló rajzok szimmetria megjelenítése // Discrete and Computational Geometry . - 1992. - T. 7 , szám. 4 . – S. 381–401 . - doi : 10.1007/BF02187850 .
• Walter Didimo, Francesco Giordano, Giuseppe Liotta. Felfelé irányuló spiralitás és felfelé irányuló síkosság tesztelése // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , sz. 4 . - S. 1842-1899 . - doi : 10.1137/070696854 .
• Fabrizio Frati. Irányított fák és irányított aciklikus gráfok egyéb családjainak minimális területű síkbeli felfelé rajzain // International Journal of Computational Geometry & Applications. - 2008. - T. 18 , sz. 3 . – S. 251–271 . - doi : 10.1142/S021819590800260X .
• Ashim Garg, Roberto Tamassia. A felfelé irányuló és egyenes vonalú síkbeliség vizsgálatának számítási összetettségéről // SIAM Journal on Computing . - 2001. - T. 31 , sz. 2 . – S. 601–625 . - doi : 10.1137/S0097539794277123 .
• Patrick Healy, Karol Lynch. Két rögzített paraméterű követhető algoritmus a felfelé irányuló síkság tesztelésére // International Journal of Foundations of Computer Science. - 2006. - T. 17 , sz. 5 . – S. 1095–1114 . - doi : 10.1142/S0129054106004285 .
• Michael D. Hutton, Anna Lubiw. Egyforrású aciklikus digráfok felfelé irányuló síkrajza // SIAM Journal on Computing . - 1996. - T. 25 , sz. 2 . – S. 291–311 . - doi : 10.1137/S0097539792235906 . . A tanulmányt először a 2. ACM-SIAM Szimpóziumon mutatták be a Diszkrét Algoritmusokról, 1991-ben.
• Michael Junger, Sebastian Leipert. Síkbeli beágyazás lineáris időben // Graph Drawing (Proc. GD '99) . - 1999. - T. 1731. - S. 72–81. — (Számítástechnikai előadásjegyzetek). — ISBN 978-3-540-66904-3 . - doi : 10.1007/3-540-46648-7_7 .
• David Kelly. A síkbeli rendezett halmazok alapjai // Discrete Mathematics . - 1987. - T. 63 , sz. 2-3 . – S. 197–216 . - doi : 10.1016/0012-365X(87)90008-2 .
• Achilleas Papakostas. Extended planarity testing of outerplanar dags (extended abstract) // Grafikonrajz: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 1994. október 10–12., Proceedings. - Berlin: Springer, 1995. - T. 894. - S. 298-306. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-58950-3_385 .
• Platt CR Planar lattices and planar graphs // Journal of Combinatorial Theory . - 1976. - T. 21 , sz. 1 . – S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
• Carsten Thomassen. Síkbeli aciklikus orientált gráfok // Sorrend . - 1989. - V. 5 , sz. 4 . – S. 349–361 . - doi : 10.1007/BF00353654 . .