Малювання графів із прямими кутами

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
МПК-подання повного графа 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, то граф є планарним, і (за теоремою Фарі) будь-який планарний граф має малюнок з відрізками без перетинів. Такі малюнки автоматично потрапляють до класу МПК. Залишаються тільки два випадки — графи 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] і побудова МПК-зображення аналогічна висхідному планарному поданню[ru][10]. Однак у окремому випадку 1-зовніпланарних графів, МПК-подання можна побудувати за лінійний час[11].

Примітки[ред. | ред. код]

  1. ↑ а б в г 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. ↑ а б 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. — arXiv:1001.3117. — DOI:10.1016/j.comgeo.2011.11.008.
  • 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.
Отримано з https://uk.wikipedia.org/w/index.php?title=Малювання_графів_із_прямими_кутами&oldid=35462838