PROFILPELAJAR.COM

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

Застосування

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

Колова схема можна використати для візуалізації повного графа, а також фрагментів, таких як кластери вершин графа, двозв'язні компоненти^[1]^[4], кластери генів у графі взаємодії генів^[5] або природні підгрупи в соціальній мережі^[6]. Використовуючи кілька кіл з вершинами графів, можна застосовувати й інші методи розташування кластерів, такі як силові алгоритми візуалізації^[7].

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

Стиль ребер

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

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

Для колової схеми регулярних графів із ребрами, намальованими всередині і поза колом як дуги, кути падіння (кут із дотичною в точці) з обох боків дуги однакові, що спрощує оптимізацію кутової роздільності малюнка^[11].

Число схрещень

Деякі автори вивчають задачу пошуку перестановки вершин колової схеми, яка мінімізує число схрещень, коли всі ребра малюються всередині кола. Це число схрещень дорівнює нулю лише для зовніпланарних графів^[10]^[13]. Для інших графів його можна оптимізувати або скоротити окремо для кожної двозв'язної компоненти графа перед формуванням розв'язку, оскільки такі компоненти можна намалювати без взаємодії між ними^[13].

У загальному випадку мінімізація числа схрещень є NP-повною задачею^[14], але її можна апроксимувати з коефіцієнтом $O(\log ^{2}n)$ , де $n$ — число вершин^[15]. Розроблено також евристичні методи скорочення складності, наприклад, засновані на продуманому порядку вставляння вершин та на локальній оптимізації^[16]^[1]^[10]^[17]^[13].

Колову схему можна використати для максимізації числа схрещень. Зокрема, вибір випадкової перестановки вершин приводить до того, що схрещування відбувається з імовірністю 1/3, так що очікуване число схрещень становить близько третини від найбільшої кількості схрещень серед усіх можливих розташувань вершин. Дерандомізація цього методу дає детермінований апроксимаційний алгоритм із коефіцієнтом апроксимації, рівним трьом^[18].

Інші критерії оптимальності

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

Див. також

Хордова діаграма — концепція візуалізації інформації, тісно пов'язана з коловим розташуванням.
Planarity^[en] — комп'ютерна гра, в якій гравець має пересувати вершини випадково згенерованого планарного графа з коловим розташуванням, щоб розплутати малюнок.

Примітки

Література

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. — arXiv:1009.0579. — DOI:10.7155/jgaa.00251.
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. — arXiv:0705.3748. — DOI:10.1016/j.tcs.2008.02.032.