1-планарний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
1-планарний малюнок графа Хівуда — шість ребер мають поодинокі перетини, а решта 15 ребер не перетинаються.

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

Розфарбовування

[ред. | ред. код]

1-планарні графи першим розглядав Рінгель, який показав, що їх можна розфарбувати, не перевищуючи 7 кольорів[1]. Пізніше точне число кольорів, необхідне для розфарбовування цих графів, (у гіршому випадку) зменшено до 6[2]. 1-планарний повний граф K6 є прикладом того, що 1-планарні графи іноді можуть вимагати для розфарбовування 6 кольорів. Однак доведення достатності 6 кольорів не є простим.

Для розфарбовування вершин та граней трикутної призми потрібно 6 кольорів

До розгляду 1-планарних графів Рінгель прийшов, намагаючись розв'язати варіант задачі тотального розфарбовування для планарних графів, у якому розфарбовуються вершини та грані планарного графа так, що жодні дві суміжні вершини не мають однакового кольору і будь-які дві суміжні грані теж повинні мати різні кольори, а також повинні відрізнятися кольори вершин та суміжних їм граней. Очевидно, що це можна зробити за допомогою 8 фарб, якщо застосувати теорему про чотири фарби до графа і його двоїстого графа окремо, застосувавши два набори з 4 фарб, що не перетинаються. Однак можна отримати меншу кількість фарб, якщо сформувати допоміжний граф, що має по вершині для кожної вершини і грані початкового планарного графа, і в якому дві вершини допоміжного графа суміжні, якщо вони відповідають суміжним об'єктам заданого планарного графа. Розфарбування вершин допоміжного графа відповідає розфарбуванню початкового планарного графа. Допоміжний граф є 1-планарним, звідки випливає, що задачу Рінгеля про розфарбування вершин і граней можна розв'язати з використанням 6 кольорів[2]. Граф K6 не можна отримати як допоміжний граф у такий спосіб, проте задача розфарбовування вершин і граней іноді вимагає 6 кольорів. Наприклад, якщо розфарбовувати планарний граф трикутної призми, для її 6 вершин + 5 граней знадобиться 6 кольорів[3].

Щільність ребер

[ред. | ред. код]

Будь-який 1-планарний граф із n вершинами має не більше 4n − 8 ребер[4]. Строгіше, кожен малюнок 1-планарного графа має не більше n − 2 перетинів. Видалення одного ребра з кожної пари ребер, що перетинаються, залишає планарний граф, який має не більше 3n − 6 ребер, звідки негайно випливає межа числа ребер 4n − 8 початкового 1-планарного графа[5]. Однак, на відміну від планарних графів (для яких усі максимальні планарні графи на заданій множині вершин мають однакову кількість ребер), існують максимальні 1-планарні графи (графи, в які не можна додати ребро зі збереженням 1-планарності), які мають істотно менше від 4n − 8 ребер[6]. Межу 4n − 8 максимального можливого числа ребер в 1-планарному графі можна використати, щоб показати, що повний граф K7 із сімома вершинами не є 1-планарним, оскільки цей граф має 21 ребро, а тоді 4n − 8 = 20 < 21[7].

Кажуть, що 1-планарний граф є оптимальним 1-планарним графом, якщо він має рівно 4n − 8 ребер, тобто, максимально можливе число. В 1-планарному вкладенні оптимального 1-планарного графа неперетинні ребра обов'язково утворюють розбиття на чотирикутники (тобто утворюють поліедральний граф, у якому кожна грань є чотирикутником). Будь-яке розбиття на чотирикутники породжує 1-планарний граф додаванням двох діагоналей у кожну чотирикутну грань. Звідси випливає, що будь-який оптимальний 1-планарний граф є ейлеровим (усі його вершини мають парний ступінь), що найменший ступінь у таких графах — 6, і що будь-який оптимальний 1-планарний граф має щонайменше вісім вершин зі ступенем точно шість. Крім того, будь-який оптимальний 1-планарний граф вершинно 4-зв'язковий і будь-який 4-вершинний переріз в такому графі є циклом, що відсікає, в нижчележачому розбиття на чотирикутники[8].

Графи, що мають прямолінійні 1-планарні малюнки (тобто малюнки, в яких кожне ребро є прямолінійним відрізком і кожен відрізок перетинається максимум одним іншим ребром), мають трохи сильнішу межу 4n − 9 максимального числа ребер, яка досягається на нескінченній кількості графів[9].

Повні багачасткові графи

[ред. | ред. код]
1-планарний малюнок графа коктейль-вечірки K2,2,2,2

Повна класифікація 1-планарних повних графів, повних двочасткових графів та більш загальних повних багаточасткових графів відома. Будь-який повний двочастковий граф вигляду K2,n є 1-планарним, як і будь-який повний тричастковий граф вигляду K1,1,n. Крім цих нескінченних множин, повними багаточастковими 1-планарними графами є K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2 та його підграфи. Мінімальні повні багаточасткові графи, що не є 1-планарними, — це K3,7, K4,5, K1,3,4, K2,3,3 і K1,1,1,1,3. Наприклад, повний двочастковий граф K3,6 є 1-планарним, оскільки він є підграфом K1,1,1,6, а ось K3,7 не є 1-планарним[7].

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

[ред. | ред. код]

Перевірка, чи є граф 1-планарним, NP-повна[10][11], і задача залишається NP-повною навіть для графів, отриманих із планарних графів додаванням єдиного ребра[12] та для графів обмеженої ширини[en][13].

Завдання фіксовано-параметрично розв'язна[en], якщо параметризувати за цикломатичним числом або деревною глибиною, так що її можна розв'язати за поліноміальний час, якщо ці параметри обмежено[13].

На відміну від теореми Фарі для планарних графів, не всі 1-планарні графи можна намалювати 1-планарно з ребрами у вигляді відрізків прямих[14][15]. Однак перевірити, чи можна намалювати 1-планарний граф із прямими ребрами, можна за поліноміальний час[16]. Крім того, будь-який 3-вершинно-зв'язний 1-планарний граф має 1-планарний малюнок, у якому максимум одне ребро на зовнішній грані має злам. Такий малюнок можна побудувати за лінійний час, виходячи з 1-планарного вкладення графа[17]. 1-планарні графи мають обмежену книжкову товщину[18], але деякі 1-планарні графи, включно з K2,2,2,2, мають книжкову товщину щонайменше чотири[19].

1-планарні графи мають обмежену локальну деревну ширину, що означає, що існує (лінійна) функція f така, що 1-планарні графи діаметра d мають деревну ширину, що не перевищує f(d). Таку ж властивість мають загальніші графи, які можна вкласти в поверхню обмеженого роду з обмеженою кількістю перетинів на ребро. Вони також мають сепаратори, невелику кількість вершин, видалення яких розбиває граф на зв'язні компоненти, розмір яких становить сталу дробову частину від усього графа. Спираючись на ці властивості, численні алгоритми для планарних графів, такі як техніка Бренди Бейкер (Brenda Sue Baker — американська математикиня) для побудови апроксимаційних алгоритмів, можна розширити на 1-планарні графи. Наприклад, цей метод приводить до схеми наближення до поліноміального часу для знаходження найбільшої незалежної множини 1-планарного графа[20].

Узагальнення та пов'язані концепції

[ред. | ред. код]

Клас графів, аналогічних зовніпланарним графам для 1-планарності, називають зовні 1-планарні графи. Це графи, які можна намалювати на диску з вершинами на межі диска та з ребрами, що мають не більше одного перетину на ребро. Ці графи завжди можна намалювати (у вигляді зовні 1-планарного графа) з прямими ребрами та перетинами під прямими кутами[21]. За допомогою динамічного програмування на SPQR-дереві заданого графа перевірити, чи є граф зовні 1-планарним, можна за лінійний час[22][23]. Тризв'язні компоненти графа (вузли дерева SPQR) можуть складатися тільки з циклів, бондграфів та повних графів із 4 вершинами, звідки випливає, що зовні 1-планарні графи є планарними та мають деревну ширину максимум 3. На відміну від 1-планарних графів, зовні 1-планарні графи мають характеризацію в термінах мінорів графа — граф є зовні 1-планарним тоді й лише тоді, коли в ньому немає жодного з п'яти заборонених мінорів[23].

До класу 1-планарних графів належать графи 4-карт[en], графи, утворені зі суміжних ділянок площини з умовою, що жодна точка не лежить на межі більш ніж чотирьох ділянок (вершини (ділянки) з'єднані ребром, якщо регіони межують). І навпаки — будь-який оптимальний 1-планарний граф є графом 4-карти. Однак 1-планарні графи, які не є оптимальними 1-планарними, можуть і не бути графами карт[24].

1-планарні графи узагальнюються до k-планарних графів, у яких кожне ребро перетинається іншими ребрами не більше k разів. Рінгель визначив локальне число перетинів графа G як найменше невід'ємне k таке, що G має k-планарний малюнок. Оскільки локальне число перетинів дорівнює найбільшому степеню графа перетинів ребер оптимального малюнка, а товщину (найменшу кількість планарних графів, на які можна розкласти ребра) можна розглядати як хроматичне число графа перетинів відповідного малюнка, з теореми Брукса випливає, що товщина не більше ніж на 1 перевищує локальне число перетинів[25]. k-планарні графи з n вершинами мають не більше O(k1/2n) ребер[26] та деревну ширину O((kn)1/2)[27]. Неглибокий мінор k-планарного графа з глибиною d сам є (2d + 1)k-планарним, так що неглибокі мінори 1-планарних графів і k-планарних графів є розрідженими графами, в тому сенсі, що 1-планарні і k-планарні графи мають обмежене розширення[28].

Для непланарних графів можна також задати параметр число перетинів — найменше число ребер, які перетинаються на будь-якому малюнку графа. Граф із числом перетинів k обов'язково k-планарний, але обернене не обов'язково істинне. Наприклад, число перетинів графа Хівуда 3, але не обов'язково ці перетини повинні бути з одним ребром, він 1-планарний і його можна намалювати з одночасною опримізацією загальної кількості перетинів та перетинів на одне ребро.

Інше пов'язане поняття для непланарних графів — перекіс[en], найменша кількість ребер, які потрібно видалити, щоб зробити граф планарним.

Примітки

[ред. | ред. код]
  1. ↑ Ringel, 1965, с. 107–117.
  2. ↑ а б Бородин, 1984, с. 12–26, 108.
  3. ↑ Albertson, Mohar, 2006, с. 289–295.
  4. ↑ Schumacher, 1986, с. 291–300.
  5. ↑ Czap, Hudák, 2013.
  6. ↑ Brandenburg, Eppstein и др., 2013.
  7. ↑ а б Czap, Hudák, 2012, с. 505–512.
  8. ↑ Suzuki, 2010, с. 1527–1540.
  9. ↑ Didimo, 2013, с. 236–240.
  10. ↑ Grigoriev, Bodlaender, 2007, с. 1–11.
  11. ↑ Korzhik, Mohar, 2009, с. 302–312.
  12. ↑ Cabello, Mohar, 2012.
  13. ↑ а б Bannister, Cabello, Eppstein, 2013.
  14. ↑ Eggleton, 1986, с. 149–172.
  15. ↑ Thomassen, 1988, с. 335–341.
  16. ↑ Hong, Eades, Liotta, Poon, 2012, с. 335–346.
  17. ↑ Alam, Brandenburg, Kobourov, 2013, с. 83–94.
  18. ↑ Bekos, Bruckdorfer, Kaufmann, Raftopoulou, 2015, с. 130–141.
  19. ↑ Bekos, Kaufmann, Zielke, 2015, с. 113–125.
  20. ↑ Grigoriev, Bodlaender, 2007. Григор'єв і Бодлаєндер формулювали свої результати для графів з відомим 1-планарним вкладенням та використовували деревний розклад вкладення з перетинами, заміненими вершинамии степеня 4. Однак їхні методи можна застосувати для початкового 1-планарного графа з обмеженою локальною деревною шириною, що дозволяє застосувати метод Бейкер до них прямо, не знаючи заздалегідь вкладення.
  21. ↑ Dehkordi, Eades, 2012, с. 543–557.
  22. ↑ Hong, Eades и др., 2013, с. 71–82.
  23. ↑ а б Auer, Bachmaier и др., 2013, с. 107–118.
  24. ↑ Chen, Grigni, Papadimitriou, 2002, с. 127–138.
  25. ↑ Kainen, 1973, с. 88-95.
  26. ↑ Pach, Tóth, 1997, с. 427–439.
  27. ↑ Dujmović, Eppstein, Wood, 2015, с. 77–88.
  28. ↑ Nešetřil, Ossona de Mendez, 2012, с. 321, теорема 14.4.

Література

[ред. | ред. код]
  • Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1965. — Bd. 29. — S. 107–117. — DOI:10.1007/BF02996313.
  • Michael O. Albertson, Bojan Mohar. Coloring vertices and faces of locally planar graphs // Graphs and Combinatorics. — 2006. — Т. 22, вип. 3. — С. 289–295. — DOI:10.1007/s00373-006-0653-4.
  • H. Schumacher. Zur Struktur 1-planarer Graphen // Mathematische Nachrichten. — 1986. — Bd. 125. — S. 291–300.
  • Július Czap, Dávid Hudák. On drawings and decompositions of 1-planar graphs // Electronic Journal of Combinatorics. — 2013. — Т. 20, вип. 2.
  • Franz Josef Brandenburg, David Eppstein, Andreas Gleißner, Michael T. Goodrich, Kathrin Hanauer, Josef Reislhuber. Proc. 20th Int. Symp. Graph Drawing / Walter Didimo, Maurizio Patrignani. — 2013.
  • Yusuke Suzuki. Re-embeddings of maximum 1-planar graphs // SIAM Journal on Discrete Mathematics. — 2010. — Т. 24, вип. 4. — С. 1527–1540. — DOI:10.1137/090746835.
  • Walter Didimo. Density of straight-line 1-planar graph drawings // Information Processing Letters. — 2013. — Т. 113, вип. 7. — С. 236–240. — DOI:10.1016/j.ipl.2013.01.013.
  • Július Czap, Dávid Hudák. 1-planarity of complete multipartite graphs // Discrete Applied Mathematics. — 2012. — Т. 160, вип. 4-5. — С. 505–512. — DOI:10.1016/j.dam.2011.11.014.
  • Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вип. 1. — С. 1–11. — DOI:10.1007/s00453-007-0010-x.
  • Vladimir P. Korzhik, Bojan Mohar. Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers / Ioannis G. Tollis, Maurizio Patrignani. — Springer, 2009. — Т. 5417. — С. 302–312. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-00219-9_29.
  • Sergio Cabello, Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. — 2012. — arXiv:1203.5944. Расширенная версия статьи 17-го ACM Симпозиума по Вычислительной геометрии, 2010.
  • Michael J. Bannister, Sergio Cabello, David Eppstein. Algorithms and Data Structures Symposium (WADS 2013). — 2013.
  • Michael Bekos, Michael Kaufmann, Christian Zielke. Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015). — 2015. — С. 113–125.
  • Vida Dujmović, David Eppstein, David R. Wood. Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015). — 2015. — С. 77–88.
  • О.В. Бородин. Решение задачи Рингеля о вершинно-граневой раскраске плоских графов и о раскраске 1-планарных графов. // Методы дискретного анализа в изучении реализаций логических функций. — Новосибирск : Институт математики СО АН СССР, 1984. — Вип. 41. — С. 12–26, 108.
  • Roger B. Eggleton. Rectilinear drawings of graphs // Utilitas Mathematica. — 1986. — Т. 29. — С. 149–172.
  • Carsten Thomassen. Rectilinear drawings of graphs // Journal of Graph Theory. — 1988. — Т. 12, вип. 3. — С. 335–341. — DOI:10.1002/jgt.3190120306.
  • Seok-Hee Hong, Peter Eades, Giuseppe Liotta, Sheung-Hung Poon. Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012, Proceedings / Joachim Gudmundsson, Julián Mestre, Taso Viglas. — Springer, 2012. — Т. 7434. — С. 335–346. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-32241-9_29.
  • Md. Jawaherul Alam, Franz J. Brandenburg, Stephen G. Kobourov. Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers. — 2013. — Т. 8242. — С. 83–94. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03841-4_8.
  • Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann, Chrysanthi Raftopoulou. Algorithms – ESA 2015. — Springer, 2015. — Т. 9294. — С. 130–141. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-662-48350-3_12.
  • 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.
  • Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, Yusuke Suzuki. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff. — 2013. — Т. 8242. — С. 71–82. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03841-4_7.
  • Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03841-4_10.
  • Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. Map graphs // Journal of the ACM. — 2002. — Т. 49, вип. 2. — С. 127–138. — DOI:10.1145/506147.506148.
  • Paul Kainen. Thickness and coarseness of graphs // Abh. Math. Sem. Univ. Hamburg. — 1973. — Т. 39. — С. 88-95. — DOI:10.1007/BF02992822.
  • János Pach, Géza Tóth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вип. 3. — С. 427–439. — DOI:10.1007/BF01215922.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 321, теорема 14.4. — (Algorithms and Combinatorics) — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4.
Отримано з https://uk.wikipedia.org/w/index.php?title=1-планарний_граф&oldid=40584634