Восходящее планарное представление

Восходящее планарное представление

Этот планарный ориентированный ациклический граф не имеет восходящего планарного представления, поскольку его источник и сток не могут быть представлены на одной грани

Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах^[1][2]. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором монотонные кривые могут пересекаться, но в которых число пересечений минимально.

Описания

Направленный ациклический граф должен быть планарным, чтобы иметь восходящее планарное представление, но не всякий планарный ациклический граф имеет такое представление. Среди всех планарных направленных ациклических графов с единственным источником (вершиной, не имеющей входящих дуг) и стоком (вершиной, не имеющей исходящих дуг), графы с восходящими планарными представлениями — это st-планарные графы, планарные графы, в которых источник и сток принадлежат одной и той же грани по меньшей мере для одного планарного вложения графа. Более обще, граф G имеет восходящее планарное представление тогда и только тогда, когда он ориентированный, ациклический и является подграфом st-планарного графа на том же самом наборе вершин^[3][4][5][6].

В восходящем вложении множество входящих и исходящих дуг, инцидентных каждой вершине, следуют подряд в циклическом порядке дуг в вершине. Говорят, что планарное вложение заданного направленного ациклического графа бимодально, если оно обладает таким свойством. Кроме того, угол между двумя последовательными дугами с той же ориентацией в заданной вершине может быть помечен как малый, если он меньше ${\displaystyle \pi }$, или большой, если он больше ${\displaystyle \pi }$. Каждый сток должен иметь в точности один большой угол и любая вершина, не являющаяся ни источником, ни стоком, не должна иметь большого угла. Кроме того, каждая внутренняя грань представления должна иметь на два больше малых углов, чем больших, а внешняя грань должна иметь на два больше больших угла, чем малых углов. Правильное назначение — это разметка углов, которая удовлетворяет описанным свойствам. Любое восходящее вложение имеет правильное назначение. В обратную сторону, любой направленный ациклический граф, имеющий бимодальное планарное вложение с правильным назначением имеет восходящее планарное представление, которое может быть построено за линейное время^{[7][8][9][10]}.

Другое описание возможно для графов с единственным источником. В этом случае восходящее планарное вложение должно иметь источник на внешней грани и любой неориентированный цикл в графе должен иметь по меньшей мере одну вершину, в которой обе дуги цикла входящие (например, вершина, находящаяся на самом верху рисунка). Обратно, если вложение имеет оба этих свойства, то это эквивалентно восходящему вложению^[11][12][13].

Вычислительная сложность

Известно, что некоторые специальные случаи проверки восходящей планарности можно осуществить за полиномиальное время:

• Проверку, является ли граф st-планарным, можно осуществить за линейное время путём добавления ребра из s в t и проверки, является ли оставшийся граф планарным. Вдоль тех же линий можно построить восходящее планарное представление (если существует) направленного ациклического графа с единственным источником и стоком за линейное время^[14][15].
• Проверку, можно ли ориентированный граф с фиксированным планарным вложением нарисовать как восходящий планарный с совместимым вложением, можно выполнить путём проверки, что вложение является бимодальным, и моделирования задачи совместимого назначения как задачи о потоке в сети. Время работы линейно от размера входного графа и полиномиально от числа источников и стоков^{[9][10][16][17][18]}.
• Поскольку направленные полиэдральные графы имеют единственное планарное вложение, существование восходящего планарного представления для этих графов может быть проверено за полиномиальное время^[9][10][19].
• Проверка, имеет ли внешнепланарный ориентированный ациклический граф восходящее планарное представление, также полиномиальна^[20][21][22].
• Любой параллельно-последовательный граф, ориентированный согласно параллельно-последовательной структуре, является восходяще планарным. Восходящее планарное представление может быть построено прямо из параллельно-последовательного разложения графа^[23]. Более обще, произвольная ориентация неориентированных параллельно-последовательных графов может быть проверена на восходящую планарность за полиномиальное время^[24].
• Любое ориентированное дерево^[англ.] восходяще планарно^[23].
• Любой двудольный планарный граф с рёбрами, ориентированными из одной доли в другую, восходяще планарен^[23][25].
• Известен более сложный алгоритм полиномиального времени для проверки восходящей планарности графов, имеющих единственный источник, но несколько стоков, или наоборот^{[26][27][28][29]}.
• Проверка восходящей планарности может быть осуществлена за полиномиальное время, если имеется постоянное число трисвязных компонент из числа вершинных сечений и эта проверка фиксированно-параметрически разрешима^[англ.] по этим двум числам^[30][31]. Проверка также фиксированно-параметрически разрешима по цикломатическому числу входного графа^[31].
• Если y-координаты всех вершин фиксированы, то x-координаты, которые делают представление восходяще планарным, можно найти за полиномиальное время^[32].

Однако задача определения, имеет ли восходящее планарное представление планарный направленный ациклический граф с несколькими источниками и несколькими стоками, является NP-полной^[33][34][35].

Рисование прямыми отрезками и требования площади

Теорема Фари утверждает, что любой планарный граф имеет представление, в котором рёбра представлены прямолинейными отрезками, и то же самое верно для восходящего планарного представления — любой восходящий планарный граф имеет восходящее планарное представление с дугами в виде прямолинейных отрезков^[36][37]. Прямолинейное восходящее представление транзитивно сокращённого st-планарного графа может быть получено с помощью техники доминирующего рисования^[англ.] со всеми вершинами, имеющими целых координат в решётке ${\displaystyle n\times n}$^[38][37]. Однако, некоторые другие восходящие планарные графы могут потребовать экспоненциальную площадь для всех их прямолинейных восходящих планарных представлений^[36][37]. Если способ вложения фиксирован, даже направленные параллельно-серийные графы и ориентированные деревья могут потребовать экспоненциальной площади^[36][39][40].

Диаграммы Хассе

Восходящие планарные представления особо важны для диаграмм Хассе частично упорядоченных множеств, так как эти диаграммы обычно требуется рисовать в восходящем стиле. В терминах теории графов это соответствует транзитивно сокращенным направленным ациклическим графам. Такой граф можно сформировать из покрывающего отношения частичного порядка и частичный порядок сам по себе образует отношение достижимости в графе. Если частично упорядоченное множество имеет один минимальный элемент, имеет один максимальный элемент и имеет восходящее планарное представление, оно обязательно формирует решётку, множество, в котором любая пара элементов имеет единственную наибольшую нижнюю границу и единственную наименьшую верхнюю границу^[41][42]. Диаграмма Хассе решётки планарна тогда и только тогда, когда её порядковая размерность^[англ.] не превосходит двух^[43][44]. Однако некоторые частичные порядки размерности два с минимальными и максимальными элементами не имеют восходящего планарного представления (возьмём порядок, определённый транзитивным замыканием порядка ${\displaystyle a<b,a<c,b<d,b<e,c<d,c<e,d<f,e<f}$).

Примечания

1. Garg, Tamassia, 1995.
2. Di Battista, Eades, Tamassia, Tollis, 1998.
3. Garg, Tamassia, 1995, с. 111–112.
4. Di Battista, Eades, Tamassia, Tollis, 1998, с. 172–179, §6.1 Inclusion in a Planar st-Graph.
5. Di Battista, Tamassia, 1988.
6. Kelly, 1987.
7. Garg, Tamassia, 1995, с. 112–115.
8. Di Battista, Eades, Tamassia, Tollis, 1998, с. 180–188, §6.2 Angles in Upward Drawings.
9. Bertolazzi, Di Battista, 1991.
10. Bertolazzi, Di Battista, Liotta, Mannino, 1994.
11. Garg, Tamassia, 1995, с. 115.
12. Di Battista, Eades, Tamassia, Tollis, 1998, с. 209–210, §6.7.2 Forbidden Cycles for Single-Source Digraphs.
13. Thomassen, 1989.
14. Garg, Tamassia, 1995, с. 119.
15. Di Battista, Eades, Tamassia, Tollis, 1998, с. 179.
16. Garg, Tamassia, 1995, с. 119–121.
17. Di Battista, Eades, Tamassia, Tollis, 1998, с. 188–192, §6.3 Upward Planarity Testing of Embedded Digraphs.
18. Abbasi, Healy, Rextin, 2010.
19. Di Battista, Eades, Tamassia, Tollis, 1998, с. 191–192.
20. Garg, Tamassia, 1995, с. 125–126.
21. Di Battista, Eades, Tamassia, Tollis, 1998, с. 209, §6.7.1 Outerplanar Digraph.
22. Papakostas, 1995.
23. Di Battista, Eades, Tamassia, Tollis, 1998, с. 212, §6.7.4 Some Classes of Upward Planar Digraphs.
24. Didimo, Giordano, Liotta, 2009.
25. Di Battista, Liu, Rival, 1990.
26. Garg, Tamassia, 1995, с. 122–125.
27. Di Battista, Eades, Tamassia, Tollis, 1998, с. 195–200, §6.5 Optimal Upward Planarity Testing of Single-Source Digraphs.
28. Hutton, Lubiw, 1996.
29. Bertolazzi, Di Battista, Mannino, Tamassia, 1998.
30. Chan, 2004.
31. Healy, Lynch, 2006.
32. Jünger, Leipert, 1999.
33. Garg, Tamassia, 1995, с. 126–132.
34. Di Battista, Eades, Tamassia, Tollis, 1998, с. 201–209, §6.6 Upward Planarity Testing is NP-complete.
35. Garg, Tamassia, 2001.
36. Di Battista, Frati, 2012, с. 149–151, §5 Upward Drawings.
37. Di Battista, Tamassia, Tollis, 1992.
38. Di Battista, Eades, Tamassia, Tollis, 1998, с. 112–127 §4.7 Dominance Drawings.
39. Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994.
40. Frati, 2008.
41. Di Battista, Eades, Tamassia, Tollis, 1998, с. 210–212 §6.7.3 Forbidden Structures for Lattices.
42. Platt, 1976.
43. Garg, Tamassia, 1995, с. 118.
44. Baker, Fishburn, Roberts, 1972.

Литература

Обзоры и учебники

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Flow and Upward Planarity // Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 171–213. — ISBN 978-0-13-301615-4.
• Giuseppe Di Battista, Fabrizio Frati. Drawing trees, outerplanar graphs, series-parallel graphs, and planar graphs in small area // Thirty Essays on Geometric Graph Theory. — Springer, 2012. — Т. 29. — С. 121–165. — (Algorithms and combinatorics). — ISBN 9781461401100. — doi:10.1007/978-1-4614-0110-0_9.
• Ashim Garg, Roberto Tamassia. Upward planarity testing // Order. — 1995. — Т. 12, вып. 2. — С. 109–133. — doi:10.1007/BF01108622.

Исследовательские работы

• Sarmad Abbasi, Patrick Healy, Aimal Rextin. Improving the running time of embedded upward planarity testing // Information Processing Letters. — 2010. — Т. 110, вып. 7. — С. 274–278. — doi:10.1016/j.ipl.2010.02.004.
• Baker K. A., Fishburn P. C., Roberts F. S. Partial orders of dimension 2 // Networks. — 1972. — Т. 2, вып. 1. — С. 11–28. — doi:10.1002/net.3230020103.
• Paola Bertolazzi, Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. How to draw a series-parallel digraph // International Journal of Computational Geometry & Applications. — 1994. — Т. 4, вып. 4. — С. 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. — С. 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. — Т. 12, вып. 6. — С. 476–497. — doi:10.1007/BF01188716.
• Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia. Optimal upward planarity testing of single-source digraphs // SIAM Journal on Computing. — 1998. — Т. 27, вып. 1. — С. 132–169. — doi:10.1137/S0097539794279626.
• Hubert Chan. A parameterized algorithm for upward planarity testing // Proc. 12th European Symposium on Algorithms (ESA '04). — Springer-Verlag, 2004. — Т. 3221. — С. 157–168. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-30140-0_16.
• Giuseppe Di Battista, Wei-Ping Liu, Ivan Rival. Bipartite graphs, upward drawings, and planarity // Information Processing Letters. — 1990. — Т. 36, вып. 6. — С. 317–322. — doi:10.1016/0020-0190(90)90045-Y.
• Giuseppe Di Battista, Roberto Tamassia. Algorithms for plane representations of acyclic digraphs // Theoretical Computer Science. — 1988. — Т. 61, вып. 2—3. — С. 175–198. — doi:10.1016/0304-3975(88)90123-5.
• Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Area requirement and symmetry display of planar upward drawings // Discrete and Computational Geometry. — 1992. — Т. 7, вып. 4. — С. 381–401. — doi:10.1007/BF02187850.
• Walter Didimo, Francesco Giordano, Giuseppe Liotta. Upward spirality and upward planarity testing // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вып. 4. — С. 1842–1899. — doi:10.1137/070696854.
• Fabrizio Frati. On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs // International Journal of Computational Geometry & Applications. — 2008. — Т. 18, вып. 3. — С. 251–271. — doi:10.1142/S021819590800260X.
• Ashim Garg, Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing // SIAM Journal on Computing. — 2001. — Т. 31, вып. 2. — С. 601–625. — doi:10.1137/S0097539794277123.
• Patrick Healy, Karol Lynch. Two fixed-parameter tractable algorithms for testing upward planarity // International Journal of Foundations of Computer Science. — 2006. — Т. 17, вып. 5. — С. 1095–1114. — doi:10.1142/S0129054106004285.
• Michael D. Hutton, Anna Lubiw. Upward planar drawing of single-source acyclic digraphs // SIAM Journal on Computing. — 1996. — Т. 25, вып. 2. — С. 291–311. — doi:10.1137/S0097539792235906.. Впервые доклад был представлен на 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
• Michael Jünger, Sebastian Leipert. Level planar embedding in linear time // Graph Drawing (Proc. GD '99). — 1999. — Т. 1731. — С. 72–81. — (Lecture Notes in Computer Science). — ISBN 978-3-540-66904-3. — doi:10.1007/3-540-46648-7_7.
• David Kelly. Fundamentals of planar ordered sets // Discrete Mathematics. — 1987. — Т. 63, вып. 2—3. — С. 197–216. — doi:10.1016/0012-365X(87)90008-2.
• Achilleas Papakostas. Upward planarity testing of outerplanar dags (extended abstract) // Graph Drawing: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. — Berlin: Springer, 1995. — Т. 894. — С. 298–306. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-58950-3_385.
• Platt C. R. Planar lattices and planar graphs // Journal of Combinatorial Theory. — 1976. — Т. 21, вып. 1. — С. 30–39. — doi:10.1016/0095-8956(76)90024-1..
• Carsten Thomassen. Planar acyclic oriented graphs // Order. — 1989. — Т. 5, вып. 4. — С. 349–361. — doi:10.1007/BF00353654..