Stigande plan representation

En stigande plan representation av en riktad acyklisk graf  är en inbäddning av grafen i det euklidiska rummet , där kanterna representeras som icke-korsande monotont ökande kurvor. Det vill säga, en kurva som representerar vilken kant som helst måste ha egenskapen att vilken horisontell linje som helst skär den vid en punkt, och inga två kanter kan skära utom vid ändarna [1] [2] . I denna mening är det ett idealiskt fall för skiktad grafritning , en stil med grafrepresentation där monotona kurvor kan skära varandra, men där antalet skärningar är minimalt.

Beskrivningar

En riktad acyklisk graf måste vara plan för att ha en stigande plan representation, men inte varje plan acyklisk graf har en sådan representation. Bland alla planriktade acykliska grafer med en enda källa (en vertex som inte har några inkommande bågar) och en sänka (en vertex som inte har några utgående bågar), är grafer med stigande plana representationer st -planära grafer , plana grafer där källan och sjunka tillhör samma och samma yta för minst en plan grafinbäddning. Mer allmänt har en graf G en stigande plan representation om och endast om den är riktad, acyklisk, och är en subgraf till en st -planär graf på samma uppsättning hörn [3] [4] [5] [6] .

I en stigande häckning följer uppsättningen av inkommande och utgående bågar som faller in på varje vertex i följd i den cykliska ordningen av bågarna vid vertexen. En plan inbäddning av en given riktad acyklisk graf sägs vara bimodal om den har denna egenskap. Vinkeln mellan två på varandra följande bågar med samma orientering vid en given vertex kan också betecknas som liten om den är mindre än , eller stor om den är större än . Varje sänka måste ha exakt en stor vinkel, och varje vertex som varken är en källa eller en sänka får inte ha en stor vinkel. Dessutom måste varje inre yta av representationen ha två fler mindre vinklar än stora vinklar, och den yttre ytan måste ha två större vinklar än mindre vinklar. Den korrekta uppgiften  är märkningen av hörnen, som uppfyller de beskrivna egenskaperna. Varje uppströmsbilaga har ett giltigt syfte. Omvänt har varje riktad acyklisk graf som har en bimodal plan inbäddning med rätt tilldelning en stigande plan representation som kan byggas i linjär tid [7] [8] [9] [10] .

En annan beskrivning är möjlig för grafer med en enda källa. I det här fallet måste den uppåtriktade plana inbäddningen härröra från den yttre ytan, och varje oriktad cykel i grafen måste ha minst en vertex där båda bågarna i cykeln kommer in (till exempel vertexen högst upp i figuren ). Omvänt, om en inbäddning har båda dessa egenskaper, då är den likvärdig med en uppströms inbäddning [11] [12] [13] .

Beräkningskomplexitet

Det är känt att vissa speciella fall av kontroll av uppåtgående planaritet kan göras i polynomtid :

• Att kontrollera om en graf är st -plan kan göras i linjär tid genom att lägga till en kant från s till t och kontrollera om den återstående grafen är plan. Längs samma linjer är det möjligt att konstruera en stigande plan representation (om den finns) av en riktad acyklisk graf med en enda källa och sjunka i linjär tid [14] [15] .
• Att testa om en riktad graf med en fast plan injektion kan ritas som en stigande plan med kompatibel injektion kan göras genom att kontrollera att anslutningen är bimodal och modellera det kompatibla tilldelningsproblemet som ett nätverksflödesproblem . Körtiden är linjär i storleken på ingångsgrafen och polynom i antalet källor och sänkor [9] [10] [16] [17] [18] .
• Eftersom riktade polyedriska grafer har en enda plan inbäddning, kan förekomsten av en stigande plan representation för dessa grafer verifieras i polynomtid [9] [10] [19] .
• Att testa om en ytterplanär riktad acyklisk graf har en stigande plan representation är också polynom [20] [21] [22] .
• Varje parallell-seriell graf , orienterad enligt den parallell-seriella strukturen, är stigande plan. En stigande plan representation kan byggas direkt från en parallell-sekventiell uppdelning av en graf [23] . Mer allmänt kan en godtycklig orientering av oriktade parallell-seriegrafer testas för uppåtgående planaritet i polynomtid [24] .
• Alla orienterade träd är stigande plant [23] .
• Varje tvådelad plan graf med kanter orienterade från en del till en annan är stigande plan [23] [25] .
• En mer komplex polynomtidsalgoritm är känd för att kontrollera den stigande planariteten för grafer som har en enda källa men flera sänkor, eller vice versa [26] [27] [28] [29] .
• Stigande planaritet kan kontrolleras i polynomtid om det finns ett konstant antal trekopplade komponenter från vertexsektionerna och denna kontroll är fixparametriskt lösbar i dessa två tal [30] [31] . Kontrollen är också fast-parametriskt avgörbar i termer av det cyklomatiska numret för ingångsgrafen [31] .
• Om y -koordinaterna för alla hörn är fixerade, så kan x -koordinaterna som gör representationen stigande plan hittas i polynomtid [32] .

Problemet med att avgöra om en planriktad acyklisk graf med flera källor med flera sänkor har en stigande plan representation är NP-komplett [33] [34] [35] .

Linjeritning och areakrav

Faris sats säger att vilken plan graf som helst har en representation där kanterna representeras av linjesegment, och detsamma gäller för en stigande plan representation - varje stigande plan graf har en stigande plan representation med bågar i form av linjesegment [36 ] [37] . En rätlinjig stigande representation av en transitivt reducerad st -planär graf kan erhållas med den dominerande ritningstekniken med alla hörn som har heltalskoordinater i gittret [38] [37] . Men vissa andra stigande plana grafer kan kräva exponentiell area för alla deras rätlinjiga stigande plana representationer [36] [37] . Om inbäddningen är fixerad kan även riktade parallell-seriegrafer och riktade träd kräva exponentiell yta [36] [39] [40] .

Hasse diagram

Stigande plana representationer är särskilt viktiga för Hasse-diagram av delvis ordnade uppsättningar , eftersom dessa diagram vanligtvis måste ritas i en stigande stil. När det gäller grafteorin motsvarar detta transitivt reducerade riktade acykliska grafer. En sådan graf kan bildas från en täckande delordningsrelation, och delordningen i sig bildar en nåbarhetsrelation i grafen. Om en poset har ett minimumelement, har ett maximumelement och har en stigande plan representation, bildar den nödvändigtvis ett gitter , en uppsättning där alla elementpar har en enda största nedre gräns och en enda minsta övre gräns [41] [ 42] . Hasse-diagrammet för ett gitter är plant om och endast om dess ordinaldimension inte överstiger två [43] [44] . Vissa partiella ordningar av dimension två med minimum- och maximumelement har dock inte en stigande plan representation (vi tar den ordning som definieras av den transitiva stängningen av ordern ).

Anteckningar

1. ↑ Garg, Tamassia, 1995 .
2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 .
3. ↑ Garg, Tamassia, 1995 , sid. 111–112.
4. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 172–179, §6.1 Införande i en Planarst -Graf.
5. ↑ Di Battista, Tamassia, 1988 .
6. ↑ Kelly, 1987 .
7. ↑ Garg, Tamassia, 1995 , sid. 112–115.
8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 180–188, §6.2 Vinklar i uppåtgående ritningar.
9. ↑ 1 2 3 Bertolazzi, Di Battista, 1991 .
10. ↑ 1 2 3 Bertolazzi, Di Battista, Liotta, Mannino, 1994 .
11. ↑ Garg, Tamassia, 1995 , sid. 115.
12. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 209–210, §6.7.2 Förbjudna cykler för enkällsdiagram.
13. ↑ Thomassen, 1989 .
14. ↑ Garg, Tamassia, 1995 , sid. 119.
15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 179.
16. ↑ Garg, Tamassia, 1995 , sid. 119–121.
17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 188–192, §6.3 Uppåtgående planaritetstestning av inbäddade digrafer.
18. ↑ Abbasi, Healy, Rextin, 2010 .
19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 191–192.
20. ↑ Garg, Tamassia, 1995 , sid. 125–126.
21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 209, §6.7.1 Outerplanar Digraph.
22. ↑ Papakostas, 1995 .
23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 212, §6.7.4 Vissa klasser av uppåtgående plana digrafer.
24. ↑ Didimo, Giordano, Liotta, 2009 .
25. ↑ Di Battista, Liu, Rival, 1990 .
26. ↑ Garg, Tamassia, 1995 , sid. 122–125.
27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 195–200, §6.5 Optimal uppåtplanaritetstestning av enkällsdiagram.
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 , sid. 126–132.
34. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 201–209, §6.6 Uppåtplanaritetstestning är NP-komplett.
35. ↑ Garg, Tamassia, 2001 .
36. ↑ 1 2 3 Di Battista, Frati, 2012 , sid. 149–151, §5 Uppåtgående ritningar.
37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 112–127 §4.7 Dominansritningar.
39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
40. ↑ Frati, 2008 .
41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 210–212 §6.7.3 Förbjudna konstruktioner för gitter.
42. ↑ Platt, 1976 .
43. ↑ Garg, Tamassia, 1995 , sid. 118.
44. ↑ Baker, Fishburn, Roberts, 1972 .

Litteratur

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Flöde och uppåtplanaritet // Grafritning: Algoritmer för visualisering av grafer. - Prentice Hall , 1998. - S. 171-213. — ISBN 978-0-13-301615-4 .
• Giuseppe Di Battista, Fabrizio Frati. Rita träd, ytterplanära grafer, serieparallella grafer och plana grafer i liten yta // Thirty Essays on Geometric Graph Theory. - Springer, 2012. - T. 29. - S. 121-165. — (Algoritmer och kombinatorier). — ISBN 9781461401100 . - doi : 10.1007/978-1-4614-0110-0_9 .
• Ashim Garg, Roberto Tamassia. Uppåtgående planaritetstestning // Order . - 1995. - T. 12 , nr. 2 . — S. 109–133 . - doi : 10.1007/BF01108622 .

• Sarmad Abbasi, Patrick Healy, Aimal Rextin. Förbättra körtiden för inbäddade uppåtgående planaritetstestning // Information Processing Letters. - 2010. - T. 110 , nr. 7 . — S. 274–278 . - doi : 10.1016/j.ipl.2010.02.004 .
• Baker KA, Fishburn PC, Roberts FS Delbeställningar av dimension 2  // Nätverk. - 1972. - Vol 2 , nr. 1 . — S. 11–28 . - doi : 10.1002/net.3230020103 .
• Paola Bertolazzi, Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Hur man ritar en serieparallell digraf // International Journal of Computational Geometry & Applications. - 1994. - T. 4 , nr. 4 . — S. 385–402 . - doi : 10.1142/S0218195994000215 .
• Paola Bertolazzi, Giuseppe Di Battista. Om uppåtdragningstestning av trekopplade digrafer // 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. Uppåtriktade ritningar av trikopplade digrafer // Algorithmica . - 1994. - T. 12 , nr. 6 . — S. 476–497 . - doi : 10.1007/BF01188716 .
• Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia. Optimal planaritetstestning uppåt av digrafer med en källa // SIAM Journal on Computing . - 1998. - T. 27 , nr. 1 . — S. 132–169 . - doi : 10.1137/S0097539794279626 .
• Hubert Chan. En parametriserad algoritm för uppåtgående planaritetstestning // Proc. 12:e europeiska symposium om algoritmer (ESA '04) . - Springer-Verlag, 2004. - T. 3221. - S. 157-168. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-540-30140-0_16 .
• Giuseppe Di Battista, Wei-Ping Liu, Ivan Rival. Tvådelade grafer, ritningar uppåt och planaritet // Information Processing Letters . - 1990. - T. 36 , nr. 6 . — S. 317–322 . - doi : 10.1016/0020-0190(90)90045-Y .
• Giuseppe Di Battista, Roberto Tamassia. Algoritmer för planrepresentationer av acykliska digrafer // Teoretisk datavetenskap . - 1988. - T. 61 , nr. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
• Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Ytbehov och symmetrivisning av plana ritningar uppåt // Diskret och beräkningsgeometri . - 1992. - T. 7 , nummer. 4 . — S. 381–401 . - doi : 10.1007/BF02187850 .
• Walter Didimo, Francesco Giordano, Giuseppe Liotta. Uppåtgående spiralitet och uppåtgående planaritetstestning // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , nr. 4 . - S. 1842-1899 . - doi : 10.1137/070696854 .
• Fabrizio Frati. På minsta area plana uppåtgående ritningar av riktade träd och andra familjer av riktade acykliska grafer // International Journal of Computational Geometry & Applications. - 2008. - T. 18 , nr. 3 . — S. 251–271 . - doi : 10.1142/S021819590800260X .
• Ashim Garg, Roberto Tamassia. Om beräkningskomplexiteten hos testning av uppåtriktad och rätlinjig planaritet // SIAM Journal on Computing . - 2001. - T. 31 , nr. 2 . — S. 601–625 . - doi : 10.1137/S0097539794277123 .
• Patrick Healy, Karol Lynch. Två handhavbara algoritmer med fasta parametrar för att testa uppåtgående planaritet // International Journal of Foundations of Computer Science. - 2006. - T. 17 , nr. 5 . — S. 1095–1114 . - doi : 10.1142/S0129054106004285 .
• Michael D. Hutton, Anna Lubiw. Uppåtgående planritning av acykliska digrafer med en källa // SIAM Journal on Computing . - 1996. - T. 25 , nr. 2 . — S. 291–311 . - doi : 10.1137/S0097539792235906 . . Uppsatsen presenterades först vid det andra ACM-SIAM-symposiet om diskreta algoritmer, 1991.
• Michael Junger, Sebastian Leipert. Nivå plan inbäddning i linjär tid // Grafritning (Proc. GD '99) . - 1999. - T. 1731. - S. 72–81. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-540-66904-3 . - doi : 10.1007/3-540-46648-7_7 .
• David Kelly. Fundamentals of planar ordered sets // Diskret matematik . - 1987. - T. 63 , nr. 2-3 . — S. 197–216 . - doi : 10.1016/0012-365X(87)90008-2 .
• Achilleas Papakostas. Uppåtgående planaritetstestning av yttre planar (extended abstract) // Grafritning: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 10–12 oktober 1994, Proceedings. - Berlin: Springer, 1995. - T. 894. - S. 298-306. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/3-540-58950-3_385 .
• Platt CR Plana gitter och plana grafer // Journal of Combinatorial Theory . - 1976. - T. 21 , nr. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
• Carsten Thomassen. Plana acykliska orienterade grafer // Ordning . - 1989. - V. 5 , nr. 4 . — S. 349–361 . - doi : 10.1007/BF00353654 . .