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

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

Одночасне вкладення графів

Одночасне вкладення графів

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

Визначення

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

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

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

Одночасне геометричне вкладення

Багато результатів щодо одночасного геометричного вкладення ґрунтуються на ідеї, що декартові координати вершин двох заданих графів можна отримати із властивостей цих двох графів. Один з основних результатів такого типу — факт, що будь-які два шляхи на тій самій множині вершин завжди мають одночасне вкладення. Щоб знайти таке вкладення, можна використати позицію вершини у першому шляху як x-координати, а позицію вершини у другому шляху — як y-координати. У цьому випадку перший шлях буде намальований як x-монотонна ламана, яка автоматично не буде самоперетинатися, а другий шлях буде намальований як y-монотонна ламана.

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

Перевірка, чи допускають два графи одночасне геометричне вкладення, є NP-складною задачею. Точніше, вона NP-складна в . З доведень цього результату також випливає, що для деяких пар графів, що мають одночасне геометричне вкладення, найменша ґратка, на якій можна намалювати графи, має розмір, що залежить двічі експоненційно від розмірів графа.

Одночасне вкладення з фіксованими ребрами

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

image Нерозв'язана проблема математики:
Чи можна за поліноміальний час знайти для двох заданих графів одночасне вкладення з фіксованими ребрами?
(більше нерозв'язаних проблем математики)

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

Необмежене одночасне вкладення

Будь-які два планарні графи мають одночасне вкладення. Це можна зробити на ґратці поліноміального розміру, ребра при цьому матимуть не більше двох зламів. Будь-які два підгамільтонові графи мають одночасне вкладення з максимум одним зламом на ребро.

Примітки

  1. Bläsius, Kobourov, Rutter, 2013, с. 349–383.
  2. Bläsius, Kobourov, Rutter, 2013, с. Theorem 11.1.
  3. Bläsius, Kobourov, Rutter, 2013, с. Figure 11.2.
  4. Brass, Cenek и др., 2007, с. 117–130.
  5. Cabello, van Kreveld и др., 2011, с. 79–96.
  6. Estrella-Balderrama, Gassner, Jünger, Percan, Schaefer, Schulz, 2008, с. 280–290.
  7. Cardinal, Kusters, 2015, с. 259–272.
  8. Duncan, Eppstein, Kobourov, 2004, с. 340–346.
  9. Bläsius, Kobourov, Rutter, 2013, с. Figure 11.5.
  10. Di Giacomo, Liotta, 2007, с. 139–160.
  11. Frati, 2007, с. 108–113.
  12. Fowler, Jünger, Kobourov, Schulz, 2011, с. 385–398.
  13. Gassner, Jünger, Percan, Schaefer, Schulz, 2006, с. 325–335.
  14. Haeupler, Jampani, Lubiw, 2013, с. 147–171.
  15. Di Giacomo, Liotta, 2005.

Література

Thomas Bläsius, Stephen G. Kobourov, Ignaz Rutter. Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, 2013. — .

  • Peter Brass, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry Theory & Applications. — 2007. — Т. 36, вип. 2. — С. 117–130. — DOI:10.1016/j.comgeo.2006.05.006.
  • Sergio Cabello, Marc van Kreveld, Giuseppe Liotta, Henk Meijer, Bettina Speckmann, Kevin Verbeek. Geometric simultaneous embeddings of a graph and a matching // . — 2011. — Т. 15, вип. 1. — С. 79–96. — DOI:10.7155/jgaa.00218.
  • Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers. — Berlin : Springer, 2008. — Т. 4875. — С. 280–290. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-77537-9_28.
  • Jean Cardinal, Vincent Kusters. The complexity of simultaneous geometric graph embedding // . — 2015. — Т. 19, вип. 1. — С. 259–272.
  • Christian Duncan, David Eppstein, Stephen G. Kobourov. Proc. 20th ACM . — ACM, 2004. — С. 340–346. — DOI:10.1145/997817.997868.
  • Emilio Di Giacomo, Giuseppe Liotta. Simultaneous embedding of outerplanar graphs, paths, and cycles // International Journal of Computational Geometry & Applications. — 2007. — Т. 17, вип. 2. — С. 139–160. — DOI:10.1142/S0218195907002276.
  • Fabrizio Frati. Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18–20, 2006, Revised Papers. — Berlin : Springer, 2007. — Т. 4372. — С. 108–113. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-70904-6_12.
  • J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, Michael Schulz. Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges // Computational Geometry Theory & Applications. — 2011. — Т. 44, вип. 8. — С. 385–398. — DOI:10.1016/j.comgeo.2011.02.002.
  • Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers. — Berlin : Springer, 2006. — Т. 4271. — С. 325–335. — (Lecture Notes in Computer Science) — DOI:10.1007/11917496_29.
  • Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw. Testing simultaneous planarity when the common graph is 2-connected // . — 2013. — Т. 17, вип. 3. — С. 147–171. — DOI:10.7155/jgaa.00289.
  • Emilio Di Giacomo, Giuseppe Liotta. 21st European Workshop on Computational Geometry. — Eindhoven University of Technology, 2005.

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

Odnocha sne vkla dennya grafiv ce tehnika vizualizaciyi dvoh i bilshe riznih grafiv na tij samij mnozhini pomichenih vershin za yakoyi unikayut shreshennya reber u kozhnomu z grafiv Shreshennya mizh rebrami riznih grafiv dozvolyayutsya ne dozvoleni tilki shreshennya reber odnogo grafa ViznachennyaYaksho dozvoleno rebra malyuvati yak lamani chi krivi bud yakij planarnij graf mozhna namalyuvati bez shreshen z vershinami v dovilnih poziciyah na ploshini Yaksho vikoristati te same roztashuvannya vershin dlya dvoh grafiv otrimayemo odnochasne vkladennya dvoh grafiv Doslidzhennya z odnochasnogo vkladennya koncentruyutsya na poshuku vkladennya z nevelikim chislom pereginiv zlamiv reber abo z malim chislom shreshen reber dvoh grafiv Vivchayutsya takozh obmezheni modeli odnochasnogo vkladennya V odnochasnomu geometrichnomu vkladenni kozhen graf maye buti namalovanij planarno z reberami vidrizkami Shob garantuvati isnuvannya takogo vkladennya dovoditsya obmezhuvatis pidklasami planarnih grafiv V inshij obmezhenij modeli odnochasne vkladennya z fiksovanimi rebrami dozvoleni krivi ta vigini ale bud yake rebro nayavne v oboh grafah maye buti podzhane odniyeyu j tiyeyu zh krivoyu v podannyah oboh grafiv Yaksho isnuye odnochasne geometrichne vkladennya vono avtomatichno ye odnochasnim vkladennyam iz fiksovanimi rebrami Odnochasne vkladennya tisno pov yazane z tovshinoyu grafa minimalnim chislom planarnih pidgrafiv yaki mozhut pokriti vsi rebra zadanogo grafa i geometrichnoyu tovshinoyu minimalnim chislom koloriv dlya rozfarbuvannya reber yaki potribni dlya podannya zadanogo grafa z rebrami u viglyadi vidrizkiv za yakogo rebra odnogo koloru ne shreshuyutsya Zokrema tovshina zadanogo grafa dorivnyuye dvom yaksho rebra grafa mozhna rozbiti na dva pidgrafi sho mayut odnochasne vkladennya a geometrichna tovshina dorivnyuye dvom yaksho rebra mozhna rozbiti na dva pidgrafi yaki mayut odnochasne geometrichne vkladennya U zadachah odnochasnogo vkladennya bilshe dvoh grafiv zazvichaj vvazhayetsya sho vsi pari vhidnih grafiv mayut odni j sami shreshennya Tobto mnozhini reber i vershin utvoryuyut en Ce obmezhennya vidome yak peretin sonyashnika Odnochasne geometrichne vkladennyaBagato rezultativ shodo odnochasnogo geometrichnogo vkladennya gruntuyutsya na ideyi sho dekartovi koordinati vershin dvoh zadanih grafiv mozhna otrimati iz vlastivostej cih dvoh grafiv Odin z osnovnih rezultativ takogo tipu fakt sho bud yaki dva shlyahi na tij samij mnozhini vershin zavzhdi mayut odnochasne vkladennya Shob znajti take vkladennya mozhna vikoristati poziciyu vershini u pershomu shlyahu yak x koordinati a poziciyu vershini u drugomu shlyahu yak y koordinati U comu vipadku pershij shlyah bude namalovanij yak x monotonna lamana yaka avtomatichno ne bude samoperetinatisya a drugij shlyah bude namalovanij yak y monotonna lamana Podibnogo rodu malyuvannya rozmishuye vershini na cilochiselnij gratci rozmiri yakoyi linijno zalezhat vid rozmiru grafa Shozhe viznachene roztashuvannya takozh pracyuye yaksho obidva grafi ye gusenicyami abo obidva ye ciklami hocha rozmiri gratki budut bilshimi prote zalishayutsya linijno zalezhnimi vid rozmiriv grafa Odnochasne vkladennya v gratku sho linijno zalezhit vid rozmiriv grafa mozhlive dlya bud yakogo chisla grafiv yaki ye zirkami Inshi pari grafiv sho dozvolyayut odnochasne vkladennya ale mozhlivo sho vimagayut bilshih rozmiriv gratki ce koleso i cikl derevo i paruvannya a takozh pari grafiv u yakih najbilshij stepin dorivnyuye dvom Odnak isnuyut pari planarnogo grafa i paruvannya abo dereva i shlyahu dlya yakih odnochasnogo geometrichnogo vkladennya ne isnuye Perevirka chi dopuskayut dva grafi odnochasne geometrichne vkladennya ye NP skladnoyu zadacheyu Tochnishe vona NP skladna v Z doveden cogo rezultatu takozh viplivaye sho dlya deyakih par grafiv sho mayut odnochasne geometrichne vkladennya najmensha gratka na yakij mozhna namalyuvati grafi maye rozmir sho zalezhit dvichi eksponencijno vid rozmiriv grafa Odnochasne vkladennya z fiksovanimi rebramiDlya odnochasnogo vkladennya z fiksovanimi rebrami klasifikaciya riznih vidiv vhidnih grafiv sho zavzhdi mayut vkladennya abo inodi ne mayut vkladennya zalezhit ne tilki vid tipiv dvoh grafiv sho berut uchast a takozh vid strukturi yih peretinu Napriklad koli obidva grafi ye zovniplanarnimi i yih peretin ye linijnim lisom zavzhdi mozhna znajti take vkladennya yake maye ne bilshe odnogo zlamu na rebro z vershinami i tochkami zlamu na gratci z rozmirom sho polinomialno zalezhit vid rozmiru grafa Isnuyut prote inshi pari zovniplanarnih grafiv zi skladnishimi peretinami yaki ne mayut takogo vkladennya Mozhna takozh znajti odnochasne vkladennya z fiksovanimi rebrami dlya bud yakoyi pari planarnogo grafa ta dereva Nerozv yazana problema matematiki Chi mozhna za polinomialnij chas znajti dlya dvoh zadanih grafiv odnochasne vkladennya z fiksovanimi rebrami bilshe nerozv yazanih problem matematiki Ye vidkritoyu problema chi mozhna pereviriti isnuvannya odnochasnogo vkladennya z fiksovanimi rebrami za polinomialnij chas Odnak dlya troh i bilshe grafiv zadacha NP skladna Odnochasne vkladennya z fiksovanimi rebrami mozhna znajti yaksho take isnuye za polinomialnij chas dlya pari zovnishnoplanovih grafiv a takozh dlya pari grafiv peretin yakih dvozv yaznij Neobmezhene odnochasne vkladennyaBud yaki dva planarni grafi mayut odnochasne vkladennya Ce mozhna zrobiti na gratci polinomialnogo rozmiru rebra pri comu matimut ne bilshe dvoh zlamiv Bud yaki dva pidgamiltonovi grafi mayut odnochasne vkladennya z maksimum odnim zlamom na rebro PrimitkiBlasius Kobourov Rutter 2013 s 349 383 Blasius Kobourov Rutter 2013 s Theorem 11 1 Blasius Kobourov Rutter 2013 s Figure 11 2 Brass Cenek i dr 2007 s 117 130 Cabello van Kreveld i dr 2011 s 79 96 Estrella Balderrama Gassner Junger Percan Schaefer Schulz 2008 s 280 290 Cardinal Kusters 2015 s 259 272 Duncan Eppstein Kobourov 2004 s 340 346 Blasius Kobourov Rutter 2013 s Figure 11 5 Di Giacomo Liotta 2007 s 139 160 Frati 2007 s 108 113 Fowler Junger Kobourov Schulz 2011 s 385 398 Gassner Junger Percan Schaefer Schulz 2006 s 325 335 Haeupler Jampani Lubiw 2013 s 147 171 Di Giacomo Liotta 2005 LiteraturaThomas Blasius Stephen G Kobourov Ignaz Rutter Handbook of Graph Drawing and Visualization Roberto Tamassia CRC Press 2013 ISBN 9781420010268 Peter Brass Eowyn Cenek Christian A Duncan Alon Efrat Cesim Erten Dan P Ismailescu Stephen G Kobourov Anna Lubiw Joseph S B Mitchell On simultaneous planar graph embeddings Computational Geometry Theory amp Applications 2007 T 36 vip 2 S 117 130 DOI 10 1016 j comgeo 2006 05 006 Sergio Cabello Marc van Kreveld Giuseppe Liotta Henk Meijer Bettina Speckmann Kevin Verbeek Geometric simultaneous embeddings of a graph and a matching 2011 T 15 vip 1 S 79 96 DOI 10 7155 jgaa 00218 Alejandro Estrella Balderrama Elisabeth Gassner Michael Junger Merijam Percan Marcus Schaefer Michael Schulz Graph Drawing 15th International Symposium GD 2007 Sydney Australia September 24 26 2007 Revised Papers Berlin Springer 2008 T 4875 S 280 290 Lecture Notes in Computer Science DOI 10 1007 978 3 540 77537 9 28 Jean Cardinal Vincent Kusters The complexity of simultaneous geometric graph embedding 2015 T 19 vip 1 S 259 272 Christian Duncan David Eppstein Stephen G Kobourov Proc 20th ACM ACM 2004 S 340 346 DOI 10 1145 997817 997868 Emilio Di Giacomo Giuseppe Liotta Simultaneous embedding of outerplanar graphs paths and cycles International Journal of Computational Geometry amp Applications 2007 T 17 vip 2 S 139 160 DOI 10 1142 S0218195907002276 Fabrizio Frati Graph Drawing 14th International Symposium GD 2006 Karlsruhe Germany September 18 20 2006 Revised Papers Berlin Springer 2007 T 4372 S 108 113 Lecture Notes in Computer Science DOI 10 1007 978 3 540 70904 6 12 J Joseph Fowler Michael Junger Stephen G Kobourov Michael Schulz Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges Computational Geometry Theory amp Applications 2011 T 44 vip 8 S 385 398 DOI 10 1016 j comgeo 2011 02 002 Elisabeth Gassner Michael Junger Merijam Percan Marcus Schaefer Michael Schulz Graph Theoretic Concepts in Computer Science 32nd International Workshop WG 2006 Bergen Norway June 22 24 2006 Revised Papers Berlin Springer 2006 T 4271 S 325 335 Lecture Notes in Computer Science DOI 10 1007 11917496 29 Bernhard Haeupler Krishnam Raju Jampani Anna Lubiw Testing simultaneous planarity when the common graph is 2 connected 2013 T 17 vip 3 S 147 171 DOI 10 7155 jgaa 00289 Emilio Di Giacomo Giuseppe Liotta 21st European Workshop on Computational Geometry Eindhoven University of Technology 2005

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