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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення[ред. | ред. код]

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

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

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

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

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

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

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

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

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

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

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

Необмежене одночасне вкладення[ред. | ред. код]

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

Примітки[ред. | ред. код]

  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. — 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 & 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 // Journal of Graph Algorithms and Applications. — 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 // Journal of Graph Algorithms and Applications. — 2015. — Т. 19, вип. 1. — С. 259–272.
  • Christian Duncan, David Eppstein, Stephen G. Kobourov. Proc. 20th ACM Symposium on Computational Geometry. — 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 // Journal of Graph Algorithms and Applications. — 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.
Отримано з https://uk.wikipedia.org/w/index.php?title=Одночасне_вкладення_графів&oldid=39081018