Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Колова схема

Колова схема

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

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

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

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

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

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

Стиль ребер

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

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

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

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

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

У загальному випадку мінімізація числа схрещень є NP-повною задачею, але її можна апроксимувати з коефіцієнтом image, де image — число вершин. Розроблено також евристичні методи скорочення складності, наприклад, засновані на продуманому порядку вставляння вершин та на локальній оптимізації.

Колову схему можна використати для максимізації числа схрещень. Зокрема, вибір випадкової перестановки вершин приводить до того, що схрещування відбувається з імовірністю 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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Kolova she ma stil vizualizaciyi grafiv u yakomu vershini grafa roztashovuyutsya na koli zdebilshogo rivnomirno otzhe utvoryuyut vershini pravilnogo mnogokutnika Kolova shema grafa Hvatala Kolova shema diagrami staniv dlya protokolu granichnogo shlyuzu Poslidovna pobudova kolovoyi shemi modeli Barabashi Albert formuvannya socialnoyi merezhiZastosuvannyaKolova shema dobre pidhodit dlya merezhevih topologij zv yazku takih yak zirka abo kilce a takozh ciklichnih chastin metabolichnih merezh Dlya grafiv iz vidomim gamiltonovim ciklom kolova shema dozvolyaye zobraziti cikl u viglyadi kola take kolova shema utvoryuye bazis dlya LCF kodu gamiltonovih kubichnih grafiv Kolova shema mozhna vikoristati dlya vizualizaciyi povnogo grafa a takozh fragmentiv takih yak klasteri vershin grafa dvozv yazni komponenti klasteri geniv u grafi vzayemodiyi geniv abo prirodni pidgrupi v socialnij merezhi Vikoristovuyuchi kilka kil z vershinami grafiv mozhna zastosovuvati j inshi metodi roztashuvannya klasteriv taki yak silovi algoritmi vizualizaciyi Perevaga kolovoyi shemi v takih galuzyah yak bioinformatika abo vizualizaciya socialnih merezh polyagaye v jogo vizualnij nejtralnosti za roztashuvannya vsih vershin na rivnij vidstani odna vid odnoyi j vid centru malyunka zhoden z vuzliv ne zajmaye centralnogo privilejovanogo stanovisha Ce vazhlivo oskilki ye psihologichna tendenciya sprijmati blizki do centru vuzli yak najvazhlivishi Stil reberRebra na zobrazhenni grafa mozhut buti hordami kola dugami kil mozhlivo perpendikulyarni do kola v tochci tak sho rebra modeli roztashovuyutsya yak pryami v modeli Puankare giperbolichnoyi geometriyi abo krivimi inshih tipiv Vizualnu vidminnist mizh vnutrishnoyu ta zovnishnoyu chastinami kola v kolovij shemi mozhna vikoristati dlya rozdilennya dvoh tipiv zobrazhennya reber Napriklad algoritm kolovogo malyuvannya Gansnera ta Korena vikoristovuye grupuvannya reber useredini kola razom z deyakimi nezgrupovanimi rebrami poza kolom Dlya kolovoyi shemi regulyarnih grafiv iz rebrami namalovanimi vseredini i poza kolom yak dugi kuti padinnya kut iz dotichnoyu v tochci z oboh bokiv dugi odnakovi sho sproshuye optimizaciyu kutovoyi rozdilnosti malyunka Chislo shreshenDeyaki avtori vivchayut zadachu poshuku perestanovki vershin kolovoyi shemi yaka minimizuye chislo shreshen koli vsi rebra malyuyutsya vseredini kola Ce chislo shreshen dorivnyuye nulyu lishe dlya zovniplanarnih grafiv Dlya inshih grafiv jogo mozhna optimizuvati abo skorotiti okremo dlya kozhnoyi dvozv yaznoyi komponenti grafa pered formuvannyam rozv yazku oskilki taki komponenti mozhna namalyuvati bez vzayemodiyi mizh nimi U zagalnomu vipadku minimizaciya chisla shreshen ye NP povnoyu zadacheyu ale yiyi mozhna aproksimuvati z koeficiyentom O log 2 n displaystyle O log 2 n de n displaystyle n chislo vershin Rozrobleno takozh evristichni metodi skorochennya skladnosti napriklad zasnovani na produmanomu poryadku vstavlyannya vershin ta na lokalnij optimizaciyi Kolovu shemu mozhna vikoristati dlya maksimizaciyi chisla shreshen Zokrema vibir vipadkovoyi perestanovki vershin privodit do togo sho shreshuvannya vidbuvayetsya z imovirnistyu 1 3 tak sho ochikuvane chislo shreshen stanovit blizko tretini vid najbilshoyi kilkosti shreshen sered usih mozhlivih roztashuvan vershin Derandomizaciya cogo metodu daye determinovanij aproksimacijnij algoritm iz koeficiyentom aproksimaciyi rivnim trom Inshi kriteriyi optimalnostiTakozh iz kolovoyu shemoyu pov yazani zadachi optimizaciyi dovzhini reber kolovoyi shemi kutovoyi rozdilnosti shreshen abo shirini rozrizu najbilshoyi kilkosti reber yaki z yednuyut protilezhni dugi kola prote bagato z cih zadach NP povni Div takozhHordova diagrama koncepciya vizualizaciyi informaciyi tisno pov yazana z kolovim roztashuvannyam en komp yuterna gra v yakij gravec maye peresuvati vershini vipadkovo zgenerovanogo planarnogo grafa z kolovim roztashuvannyam shob rozplutati malyunok PrimitkiDogrusoz Madden Madden 1997 Becker Rojas 2001 Pisanski Servatius 2013 Six Tollis 1999b Symeonidis Tollis 2004 Krebs 1996 Dogrusoz Belviranli Dilek 2012 Iragne Nikolski Mathieu Auber Sherman 2005 Huang Hong Eades 2007 Six Tollis 1999a Duncan Eppstein Goodrich Kobourov Nollenburg 2012 Gansner Koren 2007 Baur Brandes 2005 Masuda Kashiwabara Nakajima Fujisawa 1987 Shahrokhi Sykora Szekely Vrt o 1995 Makinen 1988 He Sykora 2004 Verbitsky 2008 Nguyen Eades Hong Huang 2011 Dehkordi Nguyen Eades Hong 2013 LiteraturaMichael 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 T 3353 S 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 T 17 vip 5 S 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 T 7748 S 298 309 Lecture Notes in Computer Science DOI 10 1007 978 3 642 36065 7 28 Dogrusoz 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 Ugur Dogrusoz 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 T 1190 S 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 Nollenburg 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 T 4372 S 386 398 Lecture Notes in Computer Science DOI 10 1007 978 3 540 70904 6 37 H He Ondrej Sykora 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 T 11 vip 2 S 397 429 DOI 10 7155 jgaa 00152 Florian Iragne Macha Nikolski Bertrand Mathieu David Auber David Sherman ProViz protein interaction visualization and exploration 2005 T 21 vip 2 S 272 274 DOI 10 1093 bioinformatics bth494 Valdis Krebs Visualizing human networks Release 1 0 Esther Dyson s Monthly Report 1996 T 2 96 Erkki Makinen On circular layouts International Journal of Computer Mathematics 1988 T 24 vip 1 S 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 S 292 295 Kak ukazano u Baur ta 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 T 6502 S 397 399 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 40 Tomaz Pisanski Brigitte Servatius 2 3 2 Cubic graphs and LCF notation Configurations from a Graphical Viewpoint Springer 2013 S 32 ISBN 9780817683641 Farhad Shahrokhi Ondrej Sykora Laszlo A Szekely 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 T 903 S 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 T 1619 S 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 Stirin Castle Czech Republic September 15 19 1999 Proceedings Springer 1999b T 1731 S 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 T 3337 S 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 T 396 vip 1 3 S 294 300 arXiv 0705 3748 DOI 10 1016 j tcs 2008 02 032

Дата публікації:
Топ