Vzestupné rovinné zobrazení

Vzestupná rovinná reprezentace orientovaného acyklického grafu  je vložením grafu do euklidovského prostoru , ve kterém jsou hrany reprezentovány jako neprotínající se monotónně rostoucí křivky. To znamená, že křivka představující jakoukoli hranu musí mít tu vlastnost, že ji jakákoliv vodorovná čára protíná nejvýše v jednom bodě a žádné dvě hrany se nemohou protínat kromě na koncích [1] [2] . V tomto smyslu je to ideální případ pro kreslení grafů vrstev , styl znázornění grafu, ve kterém se mohou monotónní křivky protínat, ale počet průsečíků je minimální.

Popisy

Orientovaný acyklický graf musí být rovinný , aby měl vzestupnou rovinnou reprezentaci, ale ne každý rovinný acyklický graf takovou reprezentaci má. Mezi všemi planárními orientovanými acyklickými grafy s jediným zdrojem (vrchol, který nemá žádné příchozí oblouky) a sink (vrchol, který nemá žádné výstupní oblouky), jsou grafy se vzestupným rovinným zobrazením st -planární grafy , rovinné grafy, ve kterých je zdroj a jímka patří ke stejné a stejné ploše pro alespoň jedno vložení rovinného grafu. Obecněji řečeno, graf G má vzestupnou rovinnou reprezentaci právě tehdy, je-li směrovaný, acyklický a je podgrafem st - planárního grafu na stejné množině vrcholů [3] [4] [5] [6] .

Při vzestupném vnoření následuje sada příchozích a odchozích oblouků dopadajících na každý vrchol za sebou v cyklickém pořadí oblouků ve vrcholu. O rovinném vnoření daného orientovaného acyklického grafu se říká, že je bimodální , pokud má tuto vlastnost. Také úhel mezi dvěma po sobě jdoucími oblouky se stejnou orientací v daném vrcholu může být označen jako malý , pokud je menší než , nebo velký , pokud je větší než . Každý dřez musí mít přesně jeden velký úhel a žádný vrchol, který není ani zdrojem, ani dřezem, nesmí mít velký úhel. Kromě toho musí mít každá vnitřní plocha zobrazení o dva menší úhly více než hlavní úhly a vnější plocha musí mít o dva větší úhly více než vedlejší úhly. Správným přiřazením  je označení rohů, které vyhovuje popsaným vlastnostem. Jakákoli příloha proti proudu má platný účel. Naopak každý orientovaný acyklický graf, který má bimodální rovinné vnoření se správným přiřazením, má vzestupnou rovinnou reprezentaci, kterou lze sestavit v lineárním čase [7] [8] [9] [10] .

Jiný popis je možný u grafů s jedním zdrojem. V tomto případě musí horní rovinné vložení pocházet z vnější plochy a každý neorientovaný cyklus v grafu musí mít alespoň jeden vrchol, ve kterém jsou oba oblouky cyklu (například vrchol úplně nahoře na obrázku ). Naopak, pokud má vložení obě tyto vlastnosti, pak je ekvivalentní vložení upstream [11] [12] [13] .

Výpočetní složitost

Je známo, že některé speciální případy kontroly vzestupné rovinnosti lze provést v polynomiálním čase :

• Kontrolu, zda je graf st -planární, lze provést v lineárním čase přidáním hrany od s do t a kontrolou, zda je zbývající graf rovinný. Po stejných liniích je možné sestrojit vzestupnou rovinnou reprezentaci (pokud existuje) orientovaného acyklického grafu s jediným zdrojem a poklesem v lineárním čase [14] [15] .
• Testování , zda lze řízený graf s pevnou rovinnou injekcí nakreslit jako vzestupný rovinný graf s kompatibilní injekcí , lze provést kontrolou , zda je připojení bimodální , a modelováním problému kompatibilního přiřazení jako problému toku sítě . Průběh je lineární ve velikosti vstupního grafu a polynom v počtu zdrojů a záchytů [9] [10] [16] [17] [18] .
• Vzhledem k tomu, že orientované polyedrické grafy mají jediné rovinné vnoření, lze existenci vzestupné rovinné reprezentace pro tyto grafy ověřit v polynomiálním čase [9] [10] [19] .
• Testování, zda má vnější rovinný orientovaný acyklický graf vzestupnou rovinnou reprezentaci, je také polynomické [20] [21] [22] .
• Libovolný paralelně-sériový graf , orientovaný podle paralelně-sériové struktury, je vzestupně rovinný. Vzestupné rovinné zobrazení lze sestavit přímo z paralelně sekvenčního rozkladu grafu [23] . Obecněji, libovolná orientace neorientovaných paralelně-sériových grafů může být testována na vzestupnou planaritu v polynomiálním čase [24] .
• Libovolný orientovaný strom je vzestupně rovinný [23] .
• Jakýkoli bipartitní rovinný graf s hranami orientovanými z jedné části do druhé je vzestupně rovinný [23] [25] .
• Je znám složitější polynomiální časový algoritmus pro kontrolu vzestupné rovinnosti grafů, které mají jeden zdroj, ale více propadů, nebo naopak [26] [27] [28] [29] .
• Vzestupnou rovinnost lze kontrolovat v polynomiálním čase, pokud je mezi vrcholovými sekcemi konstantní počet trojspojených komponent a tato kontrola je pevně-parametricky řešitelná v těchto dvou číslech [30] [31] . Kontrola je také pevně-parametricky rozhoditelná z hlediska cyklomatického čísla vstupního grafu [31] .
• Pokud jsou y - ové souřadnice všech vrcholů pevné, pak x - ové souřadnice, které činí reprezentaci vzestupně rovinnou, lze nalézt v polynomiálním čase [32] .

Problém určení, zda má vícezdrojový, vícevýlevkový planárně orientovaný acyklický graf vzestupnou rovinnou reprezentaci, je však NP-úplný [33] [34] [35] .

Perokresba a požadavky na plochu

Fariho teorém říká, že jakýkoli rovinný graf má zobrazení, ve kterém jsou hrany reprezentovány úsečkami, a totéž platí pro vzestupné rovinné zobrazení - jakýkoli vzestupný rovinný graf má vzestupné rovinné zobrazení s oblouky ve formě úseček [36 ] [37] . Přímočarou vzestupnou reprezentaci tranzitivně redukovaného st -planárního grafu lze získat pomocí techniky dominujícího kreslení se všemi vrcholy majícími celočíselné souřadnice v mřížce [38] [37] . Některé další vzestupné rovinné grafy však mohou vyžadovat exponenciální plochu pro všechna jejich přímočará vzestupná rovinná zobrazení [36] [37] . Pokud je vložení pevné, dokonce i orientované paralelně-sériové grafy a řízené stromy mohou vyžadovat exponenciální plochu [36] [39] [40] .

Hasseovy diagramy

Vzestupná rovinná zobrazení jsou zvláště důležitá pro Hasseovy diagramy částečně uspořádaných množin , protože tyto diagramy je obvykle potřeba kreslit vzestupně. Z hlediska teorie grafů to odpovídá tranzitivně redukovaným orientovaným acyklickým grafům. Takový graf lze vytvořit z krycího vztahu dílčího řádu a samotný dílčí řád tvoří v grafu vztah dosažitelnosti . Pokud má poset jeden minimální prvek, má jeden maximální prvek a má vzestupnou rovinnou reprezentaci, nutně tvoří mřížku , množinu, ve které má jakákoliv dvojice prvků jedinou největší dolní hranici a jednu nejmenší horní hranici [41] [ 42] . Hasseův diagram mřížky je rovinný právě tehdy, když jeho ordinální rozměr nepřesahuje dva [43] [44] . Některé dílčí řády dimenze dvě s minimálními a maximálními prvky však nemají vzestupnou rovinnou reprezentaci (přebíráme řád definovaný tranzitivním uzávěrem řádu ).

Poznámky

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 , str. 172–179, §6.1 Začlenění do planárního grafu.
5. ↑ Di Battista, Tamassia, 1988 .
6. ↑ Kelly, 1987 .
7. ↑ Garg, Tamassia, 1995 , s. 112–115.
8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 180–188, §6.2 Úhly ve výkresech směrem nahoru.
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 , str. 209–210, §6.7.2 Zakázané cykly pro jednozdrojové digrafy.
13. ↑ Thomassen, 1989 .
14. ↑ Garg, Tamassia, 1995 , s. 119.
15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 179.
16. ↑ Garg, Tamassia, 1995 , s. 119–121.
17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 188–192, §6.3 Testování vzestupné planarity vložených grafů.
18. ↑ Abbasi, Healy, Rextin, 2010 .
19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 191–192.
20. ↑ Garg, Tamassia, 1995 , s. 125–126.
21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 209, §6.7.1 Outerplanar Digraph.
22. ↑ Papakostas, 1995 .
23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , str. 212, §6.7.4 Některé třídy vzestupných rovinných digrafů.
24. ↑ Didimo, Giordano, Liotta, 2009 .
25. ↑ Di Battista, Liu, Rival, 1990 .
26. ↑ Garg, Tamassia, 1995 , s. 122–125.
27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 195–200, §6.5 Testování optimální planarity směrem nahoru jednozdrojových digrafů.
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 , str. 201–209, §6.6 Testování vzestupné planarity je NP-úplné.
35. ↑ Garg, Tamassia, 2001 .
36. ↑ 1 2 3 Di Battista, Frati, 2012 , str. 149–151, §5 Výkresy směrem nahoru.
37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 112–127 §4.7 Kresby dominance.
39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
40. ↑ Frati, 2008 .
41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 210–212 §6.7.3 Zakázané struktury pro mříž.
42. ↑ Platt, 1976 .
43. ↑ Garg, Tamassia, 1995 , s. 118.
44. ↑ Baker, Fishburn, Roberts, 1972 .

Literatura

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Flow and Upward Planarity // Kreslení grafů: Algoritmy pro vizualizaci grafů. - Prentice Hall , 1998. - S. 171-213. — ISBN 978-0-13-301615-4 .
• Giuseppe Di Battista, Fabrizio Frati. Kreslení stromů, vnějších rovinných grafů, sérioparalelních grafů a rovinných grafů na malé ploše // Třicet esejí o teorii geometrických grafů. - Springer, 2012. - T. 29. - S. 121-165. — (Algoritmy a kombinatoria). — ISBN 9781461401100 . - doi : 10.1007/978-1-4614-0110-0_9 .
• Ashim Garg, Roberto Tamassia. Testování rovinnosti směrem nahoru // Objednávka . - 1995. - T. 12 , no. 2 . — S. 109–133 . - doi : 10.1007/BF01108622 .

• Sarmad Abbasi, Patrick Healy, Aimal Rextin. Zlepšení doby běhu vestavěného testování planarity směrem nahoru // Information Processing Letters. - 2010. - T. 110 , č.p. 7 . — S. 274–278 . - doi : 10.1016/j.ipl.2010.02.004 .
• Baker KA, Fishburn PC, Roberts FS Částečné objednávky dimenze 2  // Sítě. - 1972. - svazek 2 , č. 1 . — S. 11–28 . - doi : 10.1002/net.3230020103 .
• Paola Bertolazzi, Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Jak nakreslit sérioparalelní digraf // International Journal of Computational Geometry & Applications. - 1994. - T. 4 , no. 4 . — S. 385–402 . - doi : 10.1142/S0218195994000215 .
• Paola Bertolazzi, Giuseppe Di Battista. On upward drawing testing of triconnected digraphs // 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. Upward drawings of triconnected digraphs // Algorithmica . - 1994. - T. 12 , no. 6 . — S. 476–497 . - doi : 10.1007/BF01188716 .
• Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia. Optimální testování planarity směrem nahoru jednozdrojových digrafů // SIAM Journal on Computing . - 1998. - T. 27 , no. 1 . — S. 132–169 . - doi : 10.1137/S0097539794279626 .
• Hubert Chan. Parametrizovaný algoritmus pro testování vzestupné planarity // Proc. 12. evropské sympozium o algoritmech (ESA '04) . - Springer-Verlag, 2004. - T. 3221. - S. 157-168. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-30140-0_16 .
• Giuseppe Di Battista, Wei-Ping Liu, Ivan Rival. Bipartitní grafy, vzestupné výkresy a rovinnost // Dopisy pro zpracování informací . - 1990. - T. 36 , no. 6 . — S. 317–322 . - doi : 10.1016/0020-0190(90)90045-Y .
• Giuseppe Di Battista, Roberto Tamassia. Algoritmy pro rovinné reprezentace acyklických digrafů // Teoretická informatika . - 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. Požadavek na plochu a zobrazení symetrie rovinných vzestupných výkresů // Diskrétní a výpočetní geometrie . - 1992. - T. 7 , vydání. 4 . — S. 381–401 . - doi : 10.1007/BF02187850 .
• Walter Didimo, Francesco Giordano, Giuseppe Liotta. Testování vzestupné spirály a vzestupné planarity // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , no. 4 . - S. 1842-1899 . - doi : 10.1137/070696854 .
• Fabrizio Frati. Na minimální ploše plošné výkresy orientovaných stromů a jiných rodin orientovaných acyklických grafů // International Journal of Computational Geometry & Applications. - 2008. - T. 18 , no. 3 . — S. 251–271 . - doi : 10.1142/S021819590800260X .
• Ashim Garg, Roberto Tamassia. O výpočetní složitosti testování vzestupné a přímočaré planarity // SIAM Journal on Computing . - 2001. - T. 31 , no. 2 . — S. 601–625 . - doi : 10.1137/S0097539794277123 .
• Patrick Healy, Karol Lynch. Dva upravitelné algoritmy s pevnými parametry pro testování vzestupné planarity // International Journal of Foundations of Computer Science. - 2006. - T. 17 , no. 5 . — S. 1095–1114 . - doi : 10.1142/S0129054106004285 .
• Michael D. Hutton, Anna Lubiw. Vzestupné rovinné kreslení jednozdrojových acyklických digrafů // SIAM Journal on Computing . - 1996. - T. 25 , no. 2 . — S. 291–311 . - doi : 10.1137/S0097539792235906 . . Článek byl poprvé prezentován na 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
• Michael Junger, Sebastian Leipert. Plošné plošné vkládání v lineárním čase // Kreslení grafu (Proc. GD '99) . - 1999. - T. 1731. - S. 72–81. — (Poznámky z informatiky). — ISBN 978-3-540-66904-3 . - doi : 10.1007/3-540-46648-7_7 .
• David Kelly. Základy rovinných uspořádaných množin // Diskrétní matematika . - 1987. - T. 63 , no. 2-3 . — S. 197–216 . - doi : 10.1016/0012-365X(87)90008-2 .
• Achilleas Papakostas. Testování planarity směrem nahoru u vnějších rovinných dags (rozšířený abstrakt) // Grafická kresba: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 10.–12. října 1994, Proceedings. - Berlin: Springer, 1995. - T. 894. - S. 298-306. — (Poznámky z informatiky). - doi : 10.1007/3-540-58950-3_385 .
• Platt CR Planární svazy a rovinné grafy // Journal of Combinatorial Theory . - 1976. - T. 21 , no. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
• Carsten Thomassen. Rovinné acyklické orientované grafy // Uspořádání . - 1989. - V. 5 , čís. 4 . — S. 349–361 . - doi : 10.1007/BF00353654 . .