Рисование графов под прямыми углами

Перейти к навигацииПерейти к поиску
РПУ представление полного графа K5 и полного двудольного графа K3,4

Рисование под прямыми углами (РПУ=right angle crossing, RAC) графа — это рисование, при котором вершины представлены точками, а рёбра представлены отрезками или ломаными, не более двух рёбер пересекаются в одной точке, и если два ребра пересекаются, они должны пересекаться под прямыми углами.

Стиль рисования под прямыми углами и название "RAC drawing" для этого стиля предложили Дидимо, Идес и Лиотта[1], и этот стиль возник после обнаружения, что рисунок графа с пересечением под большими углами читаются лучше, чем рисунки с малыми углами[2]. Даже для планарных графов пересечение некоторых рёбер под прямыми углами может существенно улучшить некоторые характеристики рисунка, такие как площадь или угловое разрешение[3].

Примеры

Полный граф K5 имеет РПУ рисунок с прямыми рёбрами, а вот K6, нет. Любой РПУ рисунок с 6 вершинами имеет максимум 14 рёбер, а K6 имеет 15 рёбер, слишком много для РПУ рисунка[1].

Полный двудольный граф Ka,b имеет РПУ рисунок с рёбрами в виде отрезков тогда и только тога, когда min(a,b) ≤ 2 или a + b ≤ 7. Если min(a,b) ≤ 2, то граф является планарным, и (по теореме Фари) любой планарный граф имеет рисунок в виде отрезков без пересечений. Такие рисунки автоматически попадают в класс RAC. Остаются только два случая, графы K3,3 и K3,4. Изображение K3,4 показано на рисунке. K3,3 может быть получен из K3,4 путём удаления одной вершины. Ни один из графов K4,4 и K3,5 не имеет РПУ рисунка[4].

Рёбра и изломы

Если граф с n вершинами имеет РПУ представление с рёбрами в виде отрезков, он может иметь максимум 4n − 10 рёбер. Ограничение является тесным — существуют графы с РПУ-представлением, имеющие в точности 4n − 10 рёбер[1]. Для рисунков с рёбрами в виде ломаных граница числа рёбер графа зависит от числа изломов, разрешённых на одно ребро. Графы, имеющие РПУ представления с одним или двумя изломами на ребро, имеют O(n) рёбер. Конкретнее, с одним изломом число рёбер не может превосходить 6.5n, а с двумя изломами — 74.2n[5]. Любой граф имеет РПУ-представление, если разрешено три излома на ребро[1].

Отношение к 1-планарности

Граф является 1-планарным, если он имеет рисунок с максимум одним пересечением на ребро. Интуитивно ясно, что это ограничение облегчает представление графа с пересечением рёбер под прямым углом, а ограничение 4n − 10 числа рёбер РПУ представления с рёбрами в виде отрезков близко границе 4n − 8 числа рёбер 1-планарных графов и близко границе 4n − 9 числа рёбер в представлении 1-планарных графов с рёбрами в виде отрезков. Любое РПУ представление с 4n − 10 рёбрами является 1-планарным[6][7]. Кроме того, любой 1-внешнепланарный граф (это граф с одним пересечением на ребро, в котором все вершины лежат на внешней грани рисунка) имеет РПУ представление[8]. Однако существуют 1-планарные графы с 4n − 10 рёбрами, не имеющие РПУ представления[6].

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

Задача определения, имеет ли граф РПУ представление с рёбрами в виде отрезков, является NP-трудной[9] и построение РПУ-рисунка аналогично возсходящему планарному рисованию[10]. Однако в специальном случае 1-внешнепланарных графов, РПУ-представление может быть построено за линейное время[11].

Примечания

  1. ↑ 1 2 3 4 Didimo, Eades, Liotta, 2009, с. 206–217.
  2. ↑ Huang, Hong, Eades, 2008, с. 41–46.
  3. ↑ van Kreveld, 2011, с. 371–376.
  4. ↑ Didimo, Eades, Liotta, 2010, с. 687–691.
  5. ↑ Arikushi, Fulek, Keszegh и др., 2012, с. 169–177.
  6. ↑ 1 2 Eades, Liotta, 2013, с. 961–969.
  7. ↑ Ackerman, 2014, с. 104–108.
  8. ↑ Dehkordi, Eades, 2012, с. 543–557.
  9. ↑ Argyriou, Bekos, Symvonis, 2011, с. 74–85.
  10. ↑ Angelini, Cittadini, Di Battista и др., 2010, с. 21–32.
  11. ↑ Auer, Bachmaier, Brandenburg и др., 2013, с. 107-118.

Литература

  • Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing graphs with right angle crossings // Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings. — 2009. — Т. 5664. — С. 206–217. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-03367-4_19.
  • Weidong Huang, Seok-Hee Hong, Peter Eades. Effects of crossing angles // IEEE Pacific Visualization Symposium (PacificVIS '08). — 2008. — С. 41–46. — doi:10.1109/PACIFICVIS.2008.4475457.
  • Marc van Kreveld. The quality ratio of RAC drawings and planar drawings of planar graphs // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — 2011. — Т. 6502. — С. 371–376. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-18469-7_34.
  • Walter Didimo, Peter Eades, Giuseppe Liotta. A characterization of complete bipartite RAC graphs // Information Processing Letters. — 2010. — Т. 110, вып. 16. — С. 687–691. — doi:10.1016/j.ipl.2010.05.023.
  • Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Morić, Csaba D. Tóth. Graphs that admit right angle crossing drawings // Computational Geometry Theory & Applications. — 2012. — Т. 45, вып. 4. — С. 169–177. — doi:10.1016/j.comgeo.2011.11.008. — arXiv:1001.3117.
  • Eyal Ackerman. A note on 1-planar graphs // Discrete Applied Mathematics. — 2014. — Т. 175. — С. 104–108. — doi:10.1016/j.dam.2014.05.025.
  • Hooman Reisi Dehkordi, Peter Eades. Every outer-1-plane graph has a right angle crossing drawing // International Journal of Computational Geometry & Applications. — 2012. — Т. 22, вып. 6. — С. 543–557. — doi:10.1142/S021819591250015X.
  • Peter Eades, Giuseppe Liotta. Right angle crossing graphs and 1-planarity // Discrete Applied Mathematics. — 2013. — Т. 161, вып. 7-8. — С. 961–969. — doi:10.1016/j.dam.2012.11.019.
  • Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis. The straight-line RAC drawing problem is NP-hard // SOFSEM 2011: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011, Proceedings. — 2011. — Т. 6543. — С. 74–85. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-18381-2_6.
  • Patrizio Angelini, Luca Cittadini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Michael Kaufmann, Antonios Symvonis. On the perspectives opened by right angle crossing drawings // Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. — 2010. — Т. 5849. — С. 21–32. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-11805-0_5.
  • Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Andreas Gleißner, Daniel Neuwirth, Josef Reislhuber. Recognizing Outer 1-Planar Graphs in Linear Time // Graph Drawing LNCS. — 2013. — Т. 8284. — С. 107-118. — doi:10.1007/978-3-319-03841-4.