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

У топологічній теорії графів 1 планарний граф граф який можна намалювати в евклідовій площині так що кожне ребро матиме

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

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

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

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

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

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

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

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

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

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

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

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

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

image
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-планарним.

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

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

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

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

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

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

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

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

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

Для непланарних графів можна також задати параметр число перетинів — найменше число ребер, які перетинаються на будь-якому малюнку графа. Граф із числом перетинів 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 // . — 2006. — Т. 22, вип. 3. — С. 289–295. — DOI:10.1007/s00373-006-0653-4.
  • H. Schumacher. Zur Struktur 1-planarer Graphen // . — 1986. — Bd. 125. — S. 291–300.
  • Július Czap, Dávid Hudák. On drawings and decompositions of 1-planar graphs // . — 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 // . — 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. — () — 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. . — 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 // . — 1973. — Т. 39. — С. 88-95. — DOI:10.1007/BF02992822.
  • János Pach, Géza Tóth. Graphs drawn with few crossings per edge // . — 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) — . — DOI:10.1007/978-3-642-27875-4.

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

U topologichnij teoriyi grafiv 1 planarnij graf graf yakij mozhna namalyuvati v evklidovij ploshini tak sho kozhne rebro matime ne bilshe odnogo peretinu z yedinim inshim rebrom 1 planarnij malyunok grafa Hivuda shist reber mayut poodinoki peretini a reshta 15 reber ne peretinayutsya Rozfarbovuvannya1 planarni grafi pershim rozglyadav Ringel yakij pokazav sho yih mozhna rozfarbuvati ne perevishuyuchi 7 koloriv Piznishe tochne chislo koloriv neobhidne dlya rozfarbovuvannya cih grafiv u girshomu vipadku zmensheno do 6 1 planarnij povnij graf K6 ye prikladom togo sho 1 planarni grafi inodi mozhut vimagati dlya rozfarbovuvannya 6 koloriv Odnak dovedennya dostatnosti 6 koloriv ne ye prostim Dlya rozfarbovuvannya vershin ta granej trikutnoyi prizmi potribno 6 koloriv Do rozglyadu 1 planarnih grafiv Ringel prijshov namagayuchis rozv yazati variant zadachi totalnogo rozfarbovuvannya dlya planarnih grafiv u yakomu rozfarbovuyutsya vershini ta grani planarnogo grafa tak sho zhodni dvi sumizhni vershini ne mayut odnakovogo koloru i bud yaki dvi sumizhni grani tezh povinni mati rizni kolori a takozh povinni vidriznyatisya kolori vershin ta sumizhnih yim granej Ochevidno sho ce mozhna zrobiti za dopomogoyu 8 farb yaksho zastosuvati teoremu pro chotiri farbi do grafa i jogo dvoyistogo grafa okremo zastosuvavshi dva nabori z 4 farb sho ne peretinayutsya Odnak mozhna otrimati menshu kilkist farb yaksho sformuvati dopomizhnij graf sho maye po vershini dlya kozhnoyi vershini i grani pochatkovogo planarnogo grafa i v yakomu dvi vershini dopomizhnogo grafa sumizhni yaksho voni vidpovidayut sumizhnim ob yektam zadanogo planarnogo grafa Rozfarbuvannya vershin dopomizhnogo grafa vidpovidaye rozfarbuvannyu pochatkovogo planarnogo grafa Dopomizhnij graf ye 1 planarnim zvidki viplivaye sho zadachu Ringelya pro rozfarbuvannya vershin i granej mozhna rozv yazati z vikoristannyam 6 koloriv Graf K6 ne mozhna otrimati yak dopomizhnij graf u takij sposib prote zadacha rozfarbovuvannya vershin i granej inodi vimagaye 6 koloriv Napriklad yaksho rozfarbovuvati planarnij graf trikutnoyi prizmi dlya yiyi 6 vershin 5 granej znadobitsya 6 koloriv Shilnist reberBud yakij 1 planarnij graf iz n vershinami maye ne bilshe 4n 8 reber Strogishe kozhen malyunok 1 planarnogo grafa maye ne bilshe n 2 peretiniv Vidalennya odnogo rebra z kozhnoyi pari reber sho peretinayutsya zalishaye planarnij graf yakij maye ne bilshe 3n 6 reber zvidki negajno viplivaye mezha chisla reber 4n 8 pochatkovogo 1 planarnogo grafa Odnak na vidminu vid planarnih grafiv dlya yakih usi maksimalni planarni grafi na zadanij mnozhini vershin mayut odnakovu kilkist reber isnuyut maksimalni 1 planarni grafi grafi v yaki ne mozhna dodati rebro zi zberezhennyam 1 planarnosti yaki mayut istotno menshe vid 4n 8 reber Mezhu 4n 8 maksimalnogo mozhlivogo chisla reber v 1 planarnomu grafi mozhna vikoristati shob pokazati sho povnij graf K7 iz simoma vershinami ne ye 1 planarnim oskilki cej graf maye 21 rebro a todi 4n 8 20 lt 21 Kazhut sho 1 planarnij graf ye optimalnim 1 planarnim grafom yaksho vin maye rivno 4n 8 reber tobto maksimalno mozhlive chislo V 1 planarnomu vkladenni optimalnogo 1 planarnogo grafa neperetinni rebra obov yazkovo utvoryuyut rozbittya na chotirikutniki tobto utvoryuyut poliedralnij graf u yakomu kozhna gran ye chotirikutnikom Bud yake rozbittya na chotirikutniki porodzhuye 1 planarnij graf dodavannyam dvoh diagonalej u kozhnu chotirikutnu gran Zvidsi viplivaye sho bud yakij optimalnij 1 planarnij graf ye ejlerovim usi jogo vershini mayut parnij stupin sho najmenshij stupin u takih grafah 6 i sho bud yakij optimalnij 1 planarnij graf maye shonajmenshe visim vershin zi stupenem tochno shist Krim togo bud yakij optimalnij 1 planarnij graf vershinno 4 zv yazkovij i bud yakij 4 vershinnij pereriz v takomu grafi ye ciklom sho vidsikaye v nizhchelezhachomu rozbittya na chotirikutniki Grafi sho mayut pryamolinijni 1 planarni malyunki tobto malyunki v yakih kozhne rebro ye pryamolinijnim vidrizkom i kozhen vidrizok peretinayetsya maksimum odnim inshim rebrom mayut trohi silnishu mezhu 4n 9 maksimalnogo chisla reber yaka dosyagayetsya na neskinchennij kilkosti grafiv Povni bagachastkovi grafi1 planarnij malyunok grafa koktejl vechirki K2 2 2 2 Povna klasifikaciya 1 planarnih povnih grafiv povnih dvochastkovih grafiv ta bilsh zagalnih povnih bagatochastkovih grafiv vidoma Bud yakij povnij dvochastkovij graf viglyadu K2 n ye 1 planarnim yak i bud yakij povnij trichastkovij graf viglyadu K1 1 n Krim cih neskinchennih mnozhin povnimi bagatochastkovimi 1 planarnimi grafami ye K6 K1 1 1 6 K1 1 2 3 K2 2 2 2 K1 1 1 2 2 ta jogo pidgrafi Minimalni povni bagatochastkovi grafi sho ne ye 1 planarnimi ce K3 7 K4 5 K1 3 4 K2 3 3 i K1 1 1 1 3 Napriklad povnij dvochastkovij graf K3 6 ye 1 planarnim oskilki vin ye pidgrafom K1 1 1 6 a os K3 7 ne ye 1 planarnim Obchislyuvalna skladnistPerevirka chi ye graf 1 planarnim NP povna i zadacha zalishayetsya NP povnoyu navit dlya grafiv otrimanih iz planarnih grafiv dodavannyam yedinogo rebra ta dlya grafiv obmezhenoyi en Zavdannya en yaksho parametrizuvati za ciklomatichnim chislom abo derevnoyu glibinoyu tak sho yiyi mozhna rozv yazati za polinomialnij chas yaksho ci parametri obmezheno Na vidminu vid teoremi Fari dlya planarnih grafiv ne vsi 1 planarni grafi mozhna namalyuvati 1 planarno z rebrami u viglyadi vidrizkiv pryamih Odnak pereviriti chi mozhna namalyuvati 1 planarnij graf iz pryamimi rebrami mozhna za polinomialnij chas Krim togo bud yakij 3 vershinno zv yaznij 1 planarnij graf maye 1 planarnij malyunok u yakomu maksimum odne rebro na zovnishnij grani maye Takij malyunok mozhna pobuduvati za linijnij chas vihodyachi z 1 planarnogo vkladennya grafa 1 planarni grafi mayut obmezhenu knizhkovu tovshinu ale deyaki 1 planarni grafi vklyuchno z K2 2 2 2 mayut knizhkovu tovshinu shonajmenshe chotiri 1 planarni grafi mayut obmezhenu lokalnu derevnu shirinu sho oznachaye sho isnuye linijna funkciya f taka sho 1 planarni grafi diametra d mayut derevnu shirinu sho ne perevishuye f d Taku zh vlastivist mayut zagalnishi grafi yaki mozhna vklasti v poverhnyu obmezhenogo rodu z obmezhenoyu kilkistyu peretiniv na rebro Voni takozh mayut separatori neveliku kilkist vershin vidalennya yakih rozbivaye graf na zv yazni komponenti rozmir yakih stanovit stalu drobovu chastinu vid usogo grafa Spirayuchis na ci vlastivosti chislenni algoritmi dlya planarnih grafiv taki yak tehnika Brendi Bejker Brenda Sue Baker amerikanska matematikinya dlya pobudovi aproksimacijnih algoritmiv mozhna rozshiriti na 1 planarni grafi Napriklad cej metod privodit do shemi nablizhennya do polinomialnogo chasu dlya znahodzhennya najbilshoyi nezalezhnoyi mnozhini 1 planarnogo grafa Uzagalnennya ta pov yazani koncepciyiKlas grafiv analogichnih zovniplanarnim grafam dlya 1 planarnosti nazivayut zovni 1 planarni grafi Ce grafi yaki mozhna namalyuvati na disku z vershinami na mezhi diska ta z rebrami sho mayut ne bilshe odnogo peretinu na rebro Ci grafi zavzhdi mozhna namalyuvati u viglyadi zovni 1 planarnogo grafa z pryamimi rebrami ta peretinami pid pryamimi kutami Za dopomogoyu dinamichnogo programuvannya na zadanogo grafa pereviriti chi ye graf zovni 1 planarnim mozhna za linijnij chas Trizv yazni komponenti grafa vuzli dereva SPQR mozhut skladatisya tilki z cikliv bondgrafiv ta povnih grafiv iz 4 vershinami zvidki viplivaye sho zovni 1 planarni grafi ye planarnimi ta mayut derevnu shirinu maksimum 3 Na vidminu vid 1 planarnih grafiv zovni 1 planarni grafi mayut harakterizaciyu v terminah minoriv grafa graf ye zovni 1 planarnim todi j lishe todi koli v nomu nemaye zhodnogo z p yati zaboronenih minoriv Do klasu 1 planarnih grafiv nalezhat en grafi utvoreni zi sumizhnih dilyanok ploshini z umovoyu sho zhodna tochka ne lezhit na mezhi bilsh nizh chotiroh dilyanok vershini dilyanki z yednani rebrom yaksho regioni mezhuyut I navpaki bud yakij optimalnij 1 planarnij graf ye grafom 4 karti Odnak 1 planarni grafi yaki ne ye optimalnimi 1 planarnimi mozhut i ne buti grafami kart 1 planarni grafi uzagalnyuyutsya do k planarnih grafiv u yakih kozhne rebro peretinayetsya inshimi rebrami ne bilshe k raziv Ringel viznachiv lokalne chislo peretiniv grafa G yak najmenshe nevid yemne k take sho G maye k planarnij malyunok Oskilki lokalne chislo peretiniv dorivnyuye najbilshomu stepenyu grafa peretiniv reber optimalnogo malyunka a tovshinu najmenshu kilkist planarnih grafiv na yaki mozhna rozklasti rebra mozhna rozglyadati yak hromatichne chislo grafa peretiniv vidpovidnogo malyunka z teoremi Bruksa viplivaye sho tovshina ne bilshe nizh na 1 perevishuye lokalne chislo peretiniv k planarni grafi z n vershinami mayut ne bilshe O k1 2n reber ta derevnu shirinu O kn 1 2 Neglibokij minor k planarnogo grafa z glibinoyu d sam ye 2d 1 k planarnim tak sho negliboki minori 1 planarnih grafiv i k planarnih grafiv ye rozridzhenimi grafami v tomu sensi sho 1 planarni i k planarni grafi mayut obmezhene rozshirennya Dlya neplanarnih grafiv mozhna takozh zadati parametr chislo peretiniv najmenshe chislo reber yaki peretinayutsya na bud yakomu malyunku grafa Graf iz chislom peretiniv k obov yazkovo k planarnij ale obernene ne obov yazkovo istinne Napriklad chislo peretiniv grafa Hivuda 3 ale ne obov yazkovo ci peretini povinni buti z odnim rebrom vin 1 planarnij i jogo mozhna namalyuvati z odnochasnoyu oprimizaciyeyu zagalnoyi kilkosti peretiniv ta peretiniv na odne rebro Inshe pov yazane ponyattya dlya neplanarnih grafiv en najmensha kilkist reber yaki potribno vidaliti shob zrobiti graf planarnim PrimitkiRingel 1965 s 107 117 Borodin 1984 s 12 26 108 Albertson Mohar 2006 s 289 295 Schumacher 1986 s 291 300 Czap Hudak 2013 Brandenburg Eppstein i dr 2013 Czap Hudak 2012 s 505 512 Suzuki 2010 s 1527 1540 Didimo 2013 s 236 240 Grigoriev Bodlaender 2007 s 1 11 Korzhik Mohar 2009 s 302 312 Cabello Mohar 2012 Bannister Cabello Eppstein 2013 Eggleton 1986 s 149 172 Thomassen 1988 s 335 341 Hong Eades Liotta Poon 2012 s 335 346 Alam Brandenburg Kobourov 2013 s 83 94 Bekos Bruckdorfer Kaufmann Raftopoulou 2015 s 130 141 Bekos Kaufmann Zielke 2015 s 113 125 Grigoriev Bodlaender 2007 Grigor yev i Bodlayender formulyuvali svoyi rezultati dlya grafiv z vidomim 1 planarnim vkladennyam ta vikoristovuvali derevnij rozklad vkladennya z peretinami zaminenimi vershinamii stepenya 4 Odnak yihni metodi mozhna zastosuvati dlya pochatkovogo 1 planarnogo grafa z obmezhenoyu lokalnoyu derevnoyu shirinoyu sho dozvolyaye zastosuvati metod Bejker do nih pryamo ne znayuchi zazdalegid vkladennya Dehkordi Eades 2012 s 543 557 Hong Eades i dr 2013 s 71 82 Auer Bachmaier i dr 2013 s 107 118 Chen Grigni Papadimitriou 2002 s 127 138 Kainen 1973 s 88 95 Pach Toth 1997 s 427 439 Dujmovic Eppstein Wood 2015 s 77 88 Nesetril Ossona de Mendez 2012 s 321 teorema 14 4 LiteraturaGerhard Ringel Ein Sechsfarbenproblem auf der Kugel Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg 1965 Bd 29 S 107 117 DOI 10 1007 BF02996313 Michael O Albertson Bojan Mohar Coloring vertices and faces of locally planar graphs 2006 T 22 vip 3 S 289 295 DOI 10 1007 s00373 006 0653 4 H Schumacher Zur Struktur 1 planarer Graphen 1986 Bd 125 S 291 300 Julius Czap David Hudak On drawings and decompositions of 1 planar graphs 2013 T 20 vip 2 Franz Josef Brandenburg David Eppstein Andreas Gleissner 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 T 24 vip 4 S 1527 1540 DOI 10 1137 090746835 Walter Didimo Density of straight line 1 planar graph drawings 2013 T 113 vip 7 S 236 240 DOI 10 1016 j ipl 2013 01 013 Julius Czap David Hudak 1 planarity of complete multipartite graphs Discrete Applied Mathematics 2012 T 160 vip 4 5 S 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 T 49 vip 1 S 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 T 5417 S 302 312 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 Rasshirennaya versiya stati 17 go ACM Simpoziuma po Vychislitelnoj geometrii 2010 Michael J Bannister Sergio Cabello David Eppstein 2013 Michael Bekos Michael Kaufmann Christian Zielke Proc 23rd International Symposium on Graph Drawing and Network Visualization GD 2015 2015 S 113 125 Vida Dujmovic David Eppstein David R Wood Proc 23rd International Symposium on Graph Drawing and Network Visualization GD 2015 2015 S 77 88 O V Borodin Reshenie zadachi Ringelya o vershinno granevoj raskraske ploskih grafov i o raskraske 1 planarnyh grafov Metody diskretnogo analiza v izuchenii realizacij logicheskih funkcij Novosibirsk Institut matematiki SO AN SSSR 1984 Vip 41 S 12 26 108 Roger B Eggleton Rectilinear drawings of graphs Utilitas Mathematica 1986 T 29 S 149 172 Carsten Thomassen Rectilinear drawings of graphs Journal of Graph Theory 1988 T 12 vip 3 S 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 Julian Mestre Taso Viglas Springer 2012 T 7434 S 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 T 8242 S 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 T 9294 S 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 amp Applications 2012 T 22 vip 6 S 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 T 8242 S 71 82 Lecture Notes in Computer Science DOI 10 1007 978 3 319 03841 4 7 Christopher Auer Christian Bachmaier Franz J Brandenburg Andreas Gleissner 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 T 8242 S 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 T 49 vip 2 S 127 138 DOI 10 1145 506147 506148 Paul Kainen Thickness and coarseness of graphs 1973 T 39 S 88 95 DOI 10 1007 BF02992822 Janos Pach Geza Toth Graphs drawn with few crossings per edge 1997 T 17 vip 3 S 427 439 DOI 10 1007 BF01215922 Jaroslav Nesetril Patrice Ossona de Mendez Sparsity Graphs Structures and Algorithms Springer 2012 T 28 S 321 teorema 14 4 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4

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