Круговое расположение может быть использовано для визуализации полного графа, но также может быть использовано для фрагментов, таких как кластеры вершин графа, его двусвязные компоненты[1][4], кластеры генов в графе взаимодействия генов[5] или естественные подгруппы в социальной сети[6]. Используя несколько окружностей с вершинами графов, можно применять и другие методы расположения кластеров, такие как силовые алгоритмы визуализации[7].
Преимущество кругового расположения в таких областях, как биоинформатика или визуализация социальных сетей, заключается в его визуальной нейтральности[8] — при расположении всех вершин на равном расстоянии друг от друга и от центра рисунка ни один из узлов не занимает привилегированное централизованное положение. Это важно, так как имеется психологическая тенденция воспринимать близкие к центру узлы как более важные[9].
Стиль рёбер
Рёбра на изображении графа могут представлять собой хорды окружности[10], круговые дуги[11] (возможно, перпендикулярные окружности в точке, так что рёбра модели располагаются как прямые в модели Пуанкарегиперболической геометрии) или другие типы кривых [12].
Визуальное различие между внутренней и внешней частями окружности в круговом расположении может быть использовано для разделения двух типов изображения рёбер. Например, алгоритм кругового рисования Ганснера и Корена[12] использует группировку рёбер внутри окружности вместе с некоторыми несгруппированными рёбрами вне окружности[12].
Некоторые авторы изучают задачу нахождения перестановки вершин кругового расположения, которое минимизирует число пересечений, когда все рёбра рисуются внутри окружности. Это число пересечений равно нулю только для внешнепланарных графов[10][13]. Для других графов оно может быть оптимизировано или сокращено отдельно для каждой двусвязной компоненты графа перед формированием решения, поскольку такие компоненты могут быть нарисованы без взаимодействия друг с другом[13].
В общем случае минимизация числа пересечений является NP-полной задачей[14], но она может быть аппроксимирована с коэффициентом , где n равно числу вершин[15]. Разработаны также эвристические методы сокращения сложности, например, основанные на продуманном порядке вставки вершин и на локальной оптимизации[16][1][10][17][13].
Круговое расположение может быть использовано также для максимизации числа пересечений. В частности, выбор случайной перестановки для вершин приводит к тому, что пересечение происходит с вероятностью 1/3, так что ожидаемое число пересечений может быть втрое больше максимального числа пересечений среди всех возможных расположений вершин. Дерандомизация этого метода даёт детерминированныйаппроксимационный алгоритм с коэффициентом аппроксимации, равным трём[18].
Другие критерии оптимальности
Также к задачам кругового расположения относятся оптимизация длины рёбер кругового расположения, углового разрешения пересечений или ширины разреза (максимального числа рёбер, которые соединяют дуги окружности с противоположными)[16][12][19][20]; многие из этих задач NP-полны[16].
См. также
Хордовая диаграмма — концепция визуализации информации, тесно связанная с круговым расположением.
Planarity[англ.] — компьютерная игра, в которой игрок должен передвигать вершины случайно сгенерированного планарного графа с круговым расположением, чтобы распутать рисунок.
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.
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.
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.
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.
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.
