Круговое расположение

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Круговое расположение на примере графа Хватала
Круговое расположение диаграммы состояний для протокола граничного шлюза
Последовательное построение кругового расположения для модели Барабаши — Альберт формирования социальной сети

Круговое расположение — стиль визуализации графов, при котором вершины графа располагаются на окружности, часто располагаясь равномерно, так, что они образуют вершины правильного многоугольника.

Применение[править | править код]

Круговое расположение хорошо подходит для сетевых топологий связи, таких как звезда или кольцо[1], а также для циклических частей метаболических сетей[2]. Для графов с известным гамильтоновым циклом круговое расположение позволяет отразить цикл в виде окружности; такое круговое расположение образует базис для LCF-кода гамильтоновых кубических графов[3].

Круговое расположение может быть использовано для визуализации полного графа, но также может быть использовано для фрагментов, таких как кластеры вершин графа, его двусвязные компоненты[1][4], кластеры генов в графе взаимодействия генов[5] или естественные подгруппы в социальной сети[6]. Используя несколько окружностей с вершинами графов, можно применять и другие методы расположения кластеров, такие как силовые алгоритмы визуализации[7].

Преимущество кругового расположения в таких областях, как биоинформатика или визуализация социальных сетей, заключается в его визуальной нейтральности[8] — при расположении всех вершин на равном расстоянии друг от друга и от центра рисунка ни один из узлов не занимает привилегированное централизованное положение. Это важно, так как имеется психологическая тенденция воспринимать близкие к центру узлы как более важные[9].

Стиль рёбер[править | править код]

Рёбра на изображении графа могут представлять собой хорды окружности[10], круговые дуги[11] (возможно, перпендикулярные окружности в точке, так что рёбра модели располагаются как прямые в модели Пуанкаре гиперболической геометрии) или другие типы кривых [12].

Визуальное различие между внутренней и внешней частями окружности в круговом расположении может быть использовано для разделения двух типов изображения рёбер. Например, алгоритм кругового рисования Ганснера и Корена[12] использует группировку рёбер внутри окружности вместе с некоторыми несгруппированными рёбрами вне окружности[12].

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

Число пересечений[править | править код]

Некоторые авторы изучают задачу нахождения перестановки вершин кругового расположения, которое минимизирует число пересечений, когда все рёбра рисуются внутри окружности. Это число пересечений равно нулю только для внешнепланарных графов[10][13]. Для других графов оно может быть оптимизировано или сокращено отдельно для каждой двусвязной компоненты графа перед формированием решения, поскольку такие компоненты могут быть нарисованы без взаимодействия друг с другом[13].

В общем случае минимизация числа пересечений является NP-полной задачей[14], но она может быть аппроксимирована с коэффициентом , где n равно числу вершин[15]. Разработаны также эвристические методы сокращения сложности, например, основанные на продуманном порядке вставки вершин и на локальной оптимизации[16][1][10][17][13].

Круговое расположение может быть использовано также для максимизации числа пересечений. В частности, выбор случайной перестановки для вершин приводит к тому, что пересечение происходит с вероятностью 1/3, так что ожидаемое число пересечений может быть втрое больше максимального числа пересечений среди всех возможных расположений вершин. Дерандомизация этого метода даёт детерминированный аппроксимационный алгоритм с коэффициентом аппроксимации, равным трём[18].

Другие критерии оптимальности[править | править код]

Также к задачам кругового расположения относятся оптимизация длины рёбер кругового расположения, углового разрешения пересечений или ширины разреза (максимального числа рёбер, которые соединяют дуги окружности с противоположными)[16][12][19][20]; многие из этих задач NP-полны[16].

См. также[править | править код]

  • Хордовая диаграмма — концепция визуализации информации, тесно связанная с круговым расположением.
  • Planarity[англ.] — компьютерная игра, в которой игрок должен передвигать вершины случайно сгенерированного планарного графа с круговым расположением, чтобы распутать рисунок.

Примечания[править | править код]

  1. ↑ 1 2 3 Doğrusöz, Madden, Madden, 1997.
  2. ↑ Becker, Rojas, 2001.
  3. ↑ Pisanski, Servatius, 2013.
  4. ↑ Six, Tollis, 1999b.
  5. ↑ Symeonidis, Tollis, 2004.
  6. ↑ Krebs, 1996.
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012.
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005.
  9. ↑ Huang, Hong, Eades, 2007.
  10. ↑ 1 2 3 Six, Tollis, 1999a.
  11. ↑ 1 2 Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012.
  12. ↑ 1 2 3 4 Gansner, Koren, 2007.
  13. ↑ 1 2 3 Baur, Brandes, 2005.
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987.
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995.
  16. ↑ 1 2 3 Mäkinen, 1988.
  17. ↑ He, Sýkora, 2004.
  18. ↑ Verbitsky, 2008.
  19. ↑ Nguyen, Eades, Hong, Huang, 2011.
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013.

Литература[править | править код]

  • Michael Baur, Ulrik Brandes. Crossing reduction in circular layouts // Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers / Jan van Leeuwen. — Springer, 2005. — Т. 3353. — С. 332–343. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-30559-0_28.
  • Moritz Y. Becker, Isabel Rojas. A graph layout algorithm for drawing metabolic pathways // Bioinformatics. — 2001. — Т. 17, вып. 5. — С. 461–467. — doi:10.1093/bioinformatics/17.5.461.
  • Hooman Reisi Dehkordi, Quan Nguyen, Peter Eades, Seok-Hee Hong. Circular graph drawings with large crossing angles // Algorithms and Computation: 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013, Proceedings. — Springer, 2013. — Т. 7748. — С. 298–309. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-36065-7_28.
  • Doğrusöz U., Belviranli M., Dilek A. CiSE: A circular spring embedder layout algorithm // IEEE Transactions on Visualization and Computer Graphics. — 2012. — doi:10.1109/TVCG.2012.178.
  • Uğur Doğrusöz, Brendan Madden, Patrick Madden. Circular layout in the Graph Layout toolkit // Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings. — Springer, 1997. — Т. 1190. — С. 92–100. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-62495-3_40.
  • Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Martin Nöllenburg. Lombardi drawings of graphs (англ.) // Journal of Graph Algorithms and Applications. — 2012. — Vol. 16, iss. 1. — P. 85–108. — doi:10.7155/jgaa.00251. — arXiv:1009.0579.
  • Emden R. Gansner, Yehuda Koren. Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers. — Springer, 2007. — Т. 4372. — С. 386–398. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-70904-6_37.
  • H. He, Ondrej Sýkora. New circular drawing algorithms // Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15-19. — 2004.
  • Weidong Huang, Seok-Hee Hong, Peter Eades. Effects of sociogram drawing conventions and edge crossings in social network visualization // Journal of Graph Algorithms and Applications. — 2007. — Т. 11, вып. 2. — С. 397–429. — doi:10.7155/jgaa.00152.
  • Florian Iragne, Macha Nikolski, Bertrand Mathieu, David Auber, David Sherman. ProViz: protein interaction visualization and exploration // Bioinformatics. — 2005. — Т. 21, вып. 2. — С. 272–274. — doi:10.1093/bioinformatics/bth494.
  • Valdis Krebs. Visualizing human networks // Release 1.0: Esther Dyson's Monthly Report. — 1996. — Т. 2—96.
  • Erkki Mäkinen. On circular layouts // International Journal of Computer Mathematics. — 1988. — Т. 24, вып. 1. — С. 29–37. — doi:10.1080/00207168808803629.
  • Masuda S., Kashiwabara T., Nakajima K., Fujisawa T. On the NP-completeness of a computer network layout problem // Proceedings of the IEEE International Symposium on Circuits and Systems. — 1987. — С. 292–295.. Как указано у Baur & Brandes (2005).
  • Quan Nguyen, Peter Eades, Seok-Hee Hong, Weidong Huang. Large crossing angles in circular layouts // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — Springer, 2011. — Т. 6502. — С. 397–399. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-18469-7_40.
  • Tomaž Pisanski, Brigitte Servatius. 2.3.2 Cubic graphs and LCF notation // Configurations from a Graphical Viewpoint. — Springer, 2013. — С. 32. — ISBN 9780817683641.
  • Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Book embeddings and crossing numbers // Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings. — Springer, 1995. — Т. 903. — С. 256–268. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-59071-4_53.
  • Janet M. Six, Ioannis G. Tollis. Circular drawings of biconnected graphs // Algorithm Engineering and Experimentation: International Workshop ALENEX’99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers. — Springer, 1999a. — Т. 1619. — С. 57–73. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-48518-X_4.
  • Janet M. Six, Ioannis G. Tollis. A framework for circular drawings of networks // Graph Drawing: 7th International Symposium, GD’99, Štiřín Castle, Czech Republic, September 15–19, 1999, Proceedings. — Springer, 1999b. — Т. 1731. — С. 107–116. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-46648-7_11.
  • Alkiviadis Symeonidis, Ioannis G. Tollis. Visualization of biological information with circular drawings // Biological and Medical Data Analysis: 5th International Symposium, ISBMDA 2004, Barcelona, Spain, November 18-19, 2004, Proceedings. — Springer, 2004. — Т. 3337. — С. 468–478. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-30547-7_47.
  • Oleg Verbitsky. On the obfuscation complexity of planar graphs // Theoretical Computer Science. — 2008. — Т. 396, вып. 1—3. — С. 294–300. — doi:10.1016/j.tcs.2008.02.032. — arXiv:0705.3748.
Источник — https://ru.wikipedia.org/w/index.php?title=Круговое_расположение&oldid=123479504