Круговое расположение: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Перевод с английского статьи "Circular layout"
(нет различий)

Версия от 20:25, 19 января 2019

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

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

Приложения

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