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

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

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

Применение

Круговое расположение хорошо подходит для сетевых топологий связи, таких как звезда или кольцо[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.