Колова схема

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

Колова схема графа Хватала

Колова схема діаграми станів для (протоколу граничного шлюзу)

Послідовна побудова колової схеми моделі Барабаші — Альберт формування соціальної мережі

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

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

Колова схема можна використати для візуалізації повного графа, а також фрагментів, таких як кластери вершин графа, (двозв'язні компоненти), кластери генів у графі взаємодії генів або природні підгрупи в соціальній мережі. Використовуючи кілька кіл з вершинами графів, можна застосовувати й інші методи розташування кластерів, такі як (силові алгоритми візуалізації).

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

Стиль ребер

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

1. 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. Six, Tollis, 1999a.
11. Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012.
12. Gansner, Koren, 2007.
13. Baur, Brandes, 2005.
14. Masuda, Kashiwabara, Nakajima, Fujisawa, 1987.
15. Shahrokhi, Sýkora, Székely, Vrt'o, 1995.
16. 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. — () — 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 // . — 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 // . — 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 // . — 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 // . — 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. — .
• 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 // . — 2008. — Т. 396, вип. 1—3. — С. 294–300. — arXiv:0705.3748. — DOI:10.1016/j.tcs.2008.02.032.