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

Малюва ння із прями ми кута ми МПК right angle crossing RAC графа це побудова малюнка на якому вершини подано точками а

Малювання графів із прямими кутами

Малювання графів із прямими кутами

Малюва́ння із прями́ми кута́ми (МПК=right angle crossing, RAC) графа — це побудова малюнка, на якому вершини подано точками, а ребра — відрізками або ламаними, при цьому в одній точці перетинаються не більше двох ребер, і, якщо два ребра перетинаються, то вони перетинаються під прямим кутом.

image
МПК-подання повного графа K5 і повного двочасткового графа K3,4

Стиль малювання із прямими кутами і назву «RAC drawing» для цього стилю запропонували Дідімо, Ідес і Ліотта, коли виявили, що малюнок графа з перетином під більшими кутами читається краще, ніж малюнок з малими кутами. Навіть для планарних графів перетин деяких ребер під прямими кутами може істотно поліпшити деякі характеристики малюнка, такі як площа або кутова роздільність.

Приклади

Повний граф K5 має МПК-зображення з прямими ребрами, а K6 — ні. Будь-який малюнок із прямими кутами з 6 вершинами має максимум 14 ребер, а K6 має 15 ребер, що забагато для МПК-зображення.

Повний двочастковий граф Ka,b має МПК-зображення з ребрами у вигляді відрізків тоді й лише тоді, коли min(a,b) ≤ 2 або a + b ≤ 7. Якщо min(a,b) ≤ 2, то граф є планарним, і (за теоремою Фарі) будь-який планарний граф має малюнок з відрізками без перетинів. Такі малюнки автоматично потрапляють до класу МПК. Залишаються тільки два випадки — графи K3,3 і K3,4. Зображення K3,4 показано на малюнку. K3,3 можна отримати з K3,4 видаленням однієї вершини. Жоден із графів K4,4 і K3,5 не має МПК-зображення.

Ребра і злами

Якщо граф із n вершинами має МПК-подання з ребрами у вигляді відрізків, він може мати максимум 4n − 10 ребер. Обмеження є тісним — існують графи з МПК-поданням, що мають рівно 4n − 10 ребер. Для малюнків з ребрами у вигляді ламаних межа числа ребер графа залежить від , дозволених на одне ребро. Графи, що мають МПК-подання з одним або двома зламами на ребро, мають O(n) ребер. Конкретніше, з одним зламом число ребер не може перевищувати 6.5n, а з двома зламами — 74.2n. Будь-який граф має МПК-подання, якщо дозволено три злами на ребро.

Стосунок до 1-планарності

Граф є 1-планарним, якщо він має малюнок з максимум одним перетином на ребро. Інтуїтивно ясно, що це обмеження полегшує подання графа з перетином ребер під прямим кутом, а обмеження 4n − 10 числа ребер МПК-подання з ребрами у вигляді відрізків близьке до межі 4n − 8 числа ребер 1-планарних графів і близьке до межі 4n − 9 числа ребер у поданні 1-планарних графів з ребрами у вигляді відрізків. Будь-яке МПК-подання з 4n − 10 ребрами є 1-планарним. Крім того, будь-який 1-зовніпланарний граф (це граф з одним перетином на ребро, в якому всі вершини лежать на зовнішній грані малюнка) має МПК-подання. Однак існують 1-планарні графи з 4n − 10 ребрами, що не мають МПК-подання.

Обчислювальна складність

Задача визначення, чи має граф МПК-подання з ребрами у вигляді відрізків, є NP-складною і побудова МПК-зображення аналогічна [ru]. Однак у окремому випадку 1-зовніпланарних графів, МПК-подання можна побудувати за лінійний час.

Примітки

  1. Didimo, Eades, Liotta, 2009, с. 206–217.
  2. Huang, Hong, Eades, 2008, с. 41–46.
  3. van Kreveld, 2011, с. 371–376.
  4. Didimo, Eades, Liotta, 2010, с. 687–691.
  5. Arikushi, Fulek, Keszegh и др., 2012, с. 169–177.
  6. Eades, Liotta, 2013, с. 961–969.
  7. Ackerman, 2014, с. 104–108.
  8. Dehkordi, Eades, 2012, с. 543–557.
  9. Argyriou, Bekos, Symvonis, 2011, с. 74–85.
  10. Angelini, Cittadini, Di Battista и др., 2010, с. 21–32.
  11. Auer, Bachmaier, Brandenburg и др., 2013, с. 107-118.

Література

  • Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing graphs with right angle crossings // : 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings. — 2009. — Т. 5664. — С. 206–217. — () — DOI:10.1007/978-3-642-03367-4_19.
  • Weidong Huang, Seok-Hee Hong, Peter Eades. Effects of crossing angles // IEEE Pacific Visualization Symposium (PacificVIS '08). — 2008. — С. 41–46. — DOI:10.1109/PACIFICVIS.2008.4475457.
  • Marc van Kreveld. The quality ratio of RAC drawings and planar drawings of planar graphs // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — 2011. — Т. 6502. — С. 371–376. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_34.
  • Walter Didimo, Peter Eades, Giuseppe Liotta. A characterization of complete bipartite RAC graphs // . — 2010. — Т. 110, вип. 16. — С. 687–691. — DOI:10.1016/j.ipl.2010.05.023.
  • Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Morić, Csaba D. Tóth. Graphs that admit right angle crossing drawings // Computational Geometry Theory & Applications. — 2012. — Т. 45, вип. 4. — С. 169–177. — arXiv:1001.3117. — DOI:10.1016/j.comgeo.2011.11.008.
  • Eyal Ackerman. A note on 1-planar graphs // Discrete Applied Mathematics. — 2014. — Т. 175. — С. 104–108. — DOI:10.1016/j.dam.2014.05.025.
  • Hooman Reisi Dehkordi, Peter Eades. Every outer-1-plane graph has a right angle crossing drawing // International Journal of Computational Geometry & Applications. — 2012. — Т. 22, вип. 6. — С. 543–557. — DOI:10.1142/S021819591250015X.
  • Peter Eades, Giuseppe Liotta. Right angle crossing graphs and 1-planarity // Discrete Applied Mathematics. — 2013. — Т. 161, вип. 7-8. — С. 961–969. — DOI:10.1016/j.dam.2012.11.019.
  • Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis. The straight-line RAC drawing problem is NP-hard // SOFSEM 2011: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011, Proceedings. — 2011. — Т. 6543. — С. 74–85. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18381-2_6.
  • Patrizio Angelini, Luca Cittadini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Michael Kaufmann, Antonios Symvonis. On the perspectives opened by right angle crossing drawings // Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. — 2010. — Т. 5849. — С. 21–32. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_5.
  • Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Andreas Gleißner, Daniel Neuwirth, Josef Reislhuber. Recognizing Outer 1-Planar Graphs in Linear Time // Graph Drawing LNCS. — 2013. — Т. 8284. — С. 107-118. — DOI:10.1007/978-3-319-03841-4.

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

Malyuva nnya iz pryami mi kuta mi MPK right angle crossing RAC grafa ce pobudova malyunka na yakomu vershini podano tochkami a rebra vidrizkami abo lamanimi pri comu v odnij tochci peretinayutsya ne bilshe dvoh reber i yaksho dva rebra peretinayutsya to voni peretinayutsya pid pryamim kutom MPK podannya povnogo grafa K5 i povnogo dvochastkovogo grafa K3 4 Stil malyuvannya iz pryamimi kutami i nazvu RAC drawing dlya cogo stilyu zaproponuvali Didimo Ides i Liotta koli viyavili sho malyunok grafa z peretinom pid bilshimi kutami chitayetsya krashe nizh malyunok z malimi kutami Navit dlya planarnih grafiv peretin deyakih reber pid pryamimi kutami mozhe istotno polipshiti deyaki harakteristiki malyunka taki yak plosha abo kutova rozdilnist PrikladiPovnij graf K5 maye MPK zobrazhennya z pryamimi rebrami a K6 ni Bud yakij malyunok iz pryamimi kutami z 6 vershinami maye maksimum 14 reber a K6 maye 15 reber sho zabagato dlya MPK zobrazhennya Povnij dvochastkovij graf Ka b maye MPK zobrazhennya z rebrami u viglyadi vidrizkiv todi j lishe todi koli min a b 2 abo a b 7 Yaksho min a b 2 to graf ye planarnim i za teoremoyu Fari bud yakij planarnij graf maye malyunok z vidrizkami bez peretiniv Taki malyunki avtomatichno potraplyayut do klasu MPK Zalishayutsya tilki dva vipadki grafi K3 3 i K3 4 Zobrazhennya K3 4 pokazano na malyunku K3 3 mozhna otrimati z K3 4 vidalennyam odniyeyi vershini Zhoden iz grafiv K4 4 i K3 5 ne maye MPK zobrazhennya Rebra i zlamiYaksho graf iz n vershinami maye MPK podannya z rebrami u viglyadi vidrizkiv vin mozhe mati maksimum 4n 10 reber Obmezhennya ye tisnim isnuyut grafi z MPK podannyam sho mayut rivno 4n 10 reber Dlya malyunkiv z rebrami u viglyadi lamanih mezha chisla reber grafa zalezhit vid dozvolenih na odne rebro Grafi sho mayut MPK podannya z odnim abo dvoma zlamami na rebro mayut O n reber Konkretnishe z odnim zlamom chislo reber ne mozhe perevishuvati 6 5n a z dvoma zlamami 74 2n Bud yakij graf maye MPK podannya yaksho dozvoleno tri zlami na rebro Stosunok do 1 planarnostiGraf ye 1 planarnim yaksho vin maye malyunok z maksimum odnim peretinom na rebro Intuyitivno yasno sho ce obmezhennya polegshuye podannya grafa z peretinom reber pid pryamim kutom a obmezhennya 4n 10 chisla reber MPK podannya z rebrami u viglyadi vidrizkiv blizke do mezhi 4n 8 chisla reber 1 planarnih grafiv i blizke do mezhi 4n 9 chisla reber u podanni 1 planarnih grafiv z rebrami u viglyadi vidrizkiv Bud yake MPK podannya z 4n 10 rebrami ye 1 planarnim Krim togo bud yakij 1 zovniplanarnij graf ce graf z odnim peretinom na rebro v yakomu vsi vershini lezhat na zovnishnij grani malyunka maye MPK podannya Odnak isnuyut 1 planarni grafi z 4n 10 rebrami sho ne mayut MPK podannya Obchislyuvalna skladnistZadacha viznachennya chi maye graf MPK podannya z rebrami u viglyadi vidrizkiv ye NP skladnoyu i pobudova MPK zobrazhennya analogichna ru Odnak u okremomu vipadku 1 zovniplanarnih grafiv MPK podannya mozhna pobuduvati za linijnij chas PrimitkiDidimo Eades Liotta 2009 s 206 217 Huang Hong Eades 2008 s 41 46 van Kreveld 2011 s 371 376 Didimo Eades Liotta 2010 s 687 691 Arikushi Fulek Keszegh i dr 2012 s 169 177 Eades Liotta 2013 s 961 969 Ackerman 2014 s 104 108 Dehkordi Eades 2012 s 543 557 Argyriou Bekos Symvonis 2011 s 74 85 Angelini Cittadini Di Battista i dr 2010 s 21 32 Auer Bachmaier Brandenburg i dr 2013 s 107 118 LiteraturaWalter Didimo Peter Eades Giuseppe Liotta Drawing graphs with right angle crossings 11th International Symposium WADS 2009 Banff Canada August 21 23 2009 Proceedings 2009 T 5664 S 206 217 DOI 10 1007 978 3 642 03367 4 19 Weidong Huang Seok Hee Hong Peter Eades Effects of crossing angles IEEE Pacific Visualization Symposium PacificVIS 08 2008 S 41 46 DOI 10 1109 PACIFICVIS 2008 4475457 Marc van Kreveld The quality ratio of RAC drawings and planar drawings of planar graphs Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers 2011 T 6502 S 371 376 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 34 Walter Didimo Peter Eades Giuseppe Liotta A characterization of complete bipartite RAC graphs 2010 T 110 vip 16 S 687 691 DOI 10 1016 j ipl 2010 05 023 Karin Arikushi Radoslav Fulek Balazs Keszegh Filip Moric Csaba D Toth Graphs that admit right angle crossing drawings Computational Geometry Theory amp Applications 2012 T 45 vip 4 S 169 177 arXiv 1001 3117 DOI 10 1016 j comgeo 2011 11 008 Eyal Ackerman A note on 1 planar graphs Discrete Applied Mathematics 2014 T 175 S 104 108 DOI 10 1016 j dam 2014 05 025 Hooman Reisi Dehkordi Peter Eades Every outer 1 plane graph has a right angle crossing drawing International Journal of Computational Geometry amp Applications 2012 T 22 vip 6 S 543 557 DOI 10 1142 S021819591250015X Peter Eades Giuseppe Liotta Right angle crossing graphs and 1 planarity Discrete Applied Mathematics 2013 T 161 vip 7 8 S 961 969 DOI 10 1016 j dam 2012 11 019 Evmorfia N Argyriou Michael A Bekos Antonios Symvonis The straight line RAC drawing problem is NP hard SOFSEM 2011 37th Conference on Current Trends in Theory and Practice of Computer Science Novy Smokovec Slovakia January 22 28 2011 Proceedings 2011 T 6543 S 74 85 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18381 2 6 Patrizio Angelini Luca Cittadini Giuseppe Di Battista Walter Didimo Fabrizio Frati Michael Kaufmann Antonios Symvonis On the perspectives opened by right angle crossing drawings Graph Drawing 17th International Symposium GD 2009 Chicago IL USA September 22 25 2009 Revised Papers 2010 T 5849 S 21 32 Lecture Notes in Computer Science DOI 10 1007 978 3 642 11805 0 5 Christopher Auer Christian Bachmaier Franz J Brandenburg Kathrin Hanauer Andreas Gleissner Daniel Neuwirth Josef Reislhuber Recognizing Outer 1 Planar Graphs in Linear Time Graph Drawing LNCS 2013 T 8284 S 107 118 DOI 10 1007 978 3 319 03841 4

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