Перевірка планарності

Задача перевірки планарності — це алгоритмічна задача перевірки, чи є даний граф планарним (тобто, чи можна його намалювати на площині без перетину ребер). Задачу добре вивчено в інформатиці і придумано багато практичних алгоритмів, зокрема, з використанням сучасних структур даних. Більшість цих методів працюють за час O(n) (лінійний час), де n — число ребер (або вершин) графа, що є ^[en]. Замість простого булівського значення, вихід алгоритмів перевірки планарності може дати вкладення графа, якщо граф планарний, або заваду планарності, таку як , якщо граф не планарний.

Критерії планарності

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

• Теорема Понтрягіна — Куратовського, що граф планарний тоді й лише тоді, коли він не містить підграфа, який є розбиттям K₅ (повного графа з п'ятьма вершинами) або K_3,3 ((комунальний граф), повний двочастковий граф з шістьма вершинами, три з яких з'єднані з кожною вершиною з іншої трійки).
• (Теорема Вагнера), що граф планарний тоді й лише тоді, коли він не містить (мінора) (підграфа стягувань), ізоморфного K₅ або K_3,3.
• ^[en], що описує планарні графи в термінах упорядкування зліва направо в дереві пошуку в глибину.

Критерій планарності де Фрейсекса — Розенштіля можна використати прямо як частину алгоритму перевірки планарності, тоді як теореми Куратовського і Вагнера застосовують побічно — якщо алгоритм може знайти копію K₅ або K_3,3 в даному графі, можна бути впевненим, що вхідний граф не планарний.

Є й інші критерії планарності, які описують планарні графи математично, але які менш придатні для алгоритмів перевірки планарності:

• критерій планарності Вітні, що граф планарен тоді й лише тоді, коли його ^[en] є також кографовым;
• (критерій планарності Маклейна), що описує планарні графи базисами їхніх (циклічних просторів);
• (теорема Шнайдера), що описує планарні графи ^[en] асоційованих частково впорядкованих множин;
• критерій планарності Колен де Вердьєра, що використовує спектральну теорію графів.

Алгоритм

Метод додавання шляху

Першим опублікованим (1974) алгоритмом перевірки планарності був класичний метод додавання шляху Гопкрофта і Тарджана, який працював за лінійний час. Імплементацію алгоритму Гопкрофта і Тарджана включено до ^[en] (Мельхорна), ^[en] і Неера. 2012 року Тейлор розширив цей алгоритм для генерування всіх перестановок циклічних порядків ребер для вкладення двозв'язних компонент.

Метод додавання вершин

Методи додавання вершин полягає у створенні структури даних, що представляє можливі вкладення породженого підграфа даного графа, і додавання вершин по одній до цієї структури даних. Ці методи починалися з неефективного O(n²) методу, який 1967 року запропонували Лемпель, ^[en] і Цедербаум. Метод покращили Івен і Тарджан, які знайшли розв'язок лінійного часу для кроку s,t-нумерації, а потім поліпшили Бут і Люкер, які розробили структуру даних PQ-дерево. З цими поліпшеннями метод став лінійним за часом і, практично, став працювати швидше від методу додавання шляхів. Цей метод також розширено, щоб ефективно обчислювати планарне вкладення (малювання) для планарних графів. 1999 року Ші і Сю спростили ці методи, використовуючи PC-дерево (некореневий варіант PQ-дерева) і (обхід із відкладеною вибіркою) дерева вершин з пошуком у глибину.

Метод додавання ребер

2004 року Бойєр і Мірволд розробили спрощений алгоритм з часом роботи O(n), навіяний методом PQ-дерева, але в якому позбулися PQ-дерева і алгоритм використовує додавання ребер для обчислення планарного вкладення, якщо воно можливе. В іншому випадку обчислюється розбиття Куратовського (або графа K₅, або графа K_3,3). Метод є одним з двох алгоритмів, які існують нині (другий — алгоритм перевірки планарності де Фрейсекса, де Мендеса і Розенштіля). У статті Боєра, Кортезе, Патрігнамі та Баттіста описано експериментальне порівняння з попередньою версією алгоритму перевірки планарності Боєра і Мірволда. При цьому алгоритм Боєра і Мірволда розширено для виділення декількох розбиттів Куратовського непланарного вхідного графа з часом роботи, лінійно залежним від розміру виходу. Сирці перевірки планарності і виділення декількох розбиттів Куратовського перебувають у відкритому доступі (мовою C++). Алгоритм, що визначає підграф Куратовського за лінійний від кількості вершин час, розробив Вільямсон у 1980-х роках.

Метод послідовної побудови

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

Примітки

1. Hopcroft, Tarjan, 1974, с. 549–568.
2. Mehlhorn, Mutzel, 1996, с. 233–242.
3. Mehlhorn, Mutzel, Näher, 1993.
4. Mehlhorn, Näher, 1995, с. 96–102.
5. Taylor, 2012.
6. Lempel, Even, Cederbaum, 1967, с. 215–232.
7. Even, Tarjan, 1976, с. 339–344.
8. Боєр і Мірволд (Boyer, Myrvold, 2004): «Ця імплементація в LEDA повільніша, ніж LEDA-імплементації багатьох інших алгоритмів перевірки планарності з часом O(n)».
9. Chiba, Nishizeki, Abe, Ozawa, 1985, с. 54–76.
10. Shih, Hsu, 1999, с. 179–191.
11. Boyer, Myrvold, 2004, с. 241–273.
12. de Fraysseix, Ossona de Mendez, Rosenstiehl, 2006, с. 1017–1030.
13. Brandes, 2009.
14. Boyer, Cortese, Patrignani, Battista, 2003, с. 25–36.
15. Chimani, Mutzel, Schmidt, 2008, с. 159–170.
16. OGDF — Open Graph Drawing Framework: start
17. Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding — 1.40.0
18. Williamson, 1984, с. 681–693.
19. Schmidt, 2014, с. 967–978.

Література

• John Hopcroft, Robert E. Tarjan. Efficient planarity testing // . — 1974. — Т. 21, вип. 4. — С. 549–568. — DOI:10.1145/321850.321852.
• Kurt Mehlhorn, Petra Mutzel. On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm // Algorithmica. — 1996. — Т. 16. — С. 233–242. — DOI:10.1007/bf01940648.
• Kurt Mehlhorn, Petra Mutzel, Stefan Näher. An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm. — 1993.
• Kurt Mehlhorn, Stefan Näher. LEDA: A library of efficient data types and algorithms // CACM. — 1995. — Т. 38, вип. 1. — С. 96–102.
• Martyn G. Taylor. Planarity Testing by Path Addition. — University of Kent, 2012. — (Ph.D.) Архівовано з джерела 2 березня 2014
• Lempel A., Even S., Cederbaum I. An algorithm for planarity testing of graphs // Theory of Graphs. — New York : Gordon and Breach, 1967. — С. 215–232.
• Shimon Even, Robert E. Tarjan. Computing an st-numbering // Theoretical Computer Science. — 1976. — Т. 2, вип. 3. — С. 339–344. — DOI:10.1016/0304-3975(76)90086-4.
• Chiba N., Nishizeki T., Abe A., Ozawa T. A linear algorithm for embedding planar graphs using PQ–trees // Journal of Computer and Systems Sciences. — 1985. — Т. 30, вип. 1. — С. 54–76. — DOI:10.1016/0022-0000(85)90004-2.
• Shih W. K., Hsu W. L. A new planarity test // Theoretical Computer Science. — 1999. — Т. 223, вип. 1–2. — С. 179–191. — DOI:10.1016/S0304-3975(98)00120-0.
• John M. Boyer, Wendy J. Myrvold. On the cutting edge: simplified O(n) planarity by edge addition // . — 2004. — Т. 8, вип. 3. — С. 241–273. — DOI:10.7155/jgaa.00091.
• de Fraysseix H., Ossona de Mendez P., Rosenstiehl P. Trémaux Trees and Planarity // International Journal of Foundations of Computer Science. — 2006. — Т. 17, вип. 5. — С. 1017–1030. — DOI:10.1142/S0129054106004248.
• Ulrik Brandes. The left-right planarity test. — 2009.
• Boyer J. M., Cortese P. F., Patrignani M., Battista G. D. Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm // (Proc. 11th Int. Symp. Graph Drawing (GD '03)). — Springer-Verlag, 2003. — Т. 2912. — С. 25–36. — ()
• Chimani M., Mutzel P., Schmidt J. M. Efficient extraction of multiple Kuratowski subdivisions // (Proc. 15th Int. Symp. Graph Drawing (GD'07)). — Sydney, Australia : Springer-Verlag, 2008. — Т. 4875. — С. 159–170. — (Lecture Notes in Computer Science)
• S. G. Williamson. Depth First Search and Kuratowski Subgraphs // Journal of the ACM. — 1984. — Т. 31. — С. 681–693. — DOI:10.1145/1634.322451.
• Jens M. Schmidt. The Mondshein Sequence // Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14). — 2014. — С. 967–978. — DOI:10.1007/978-3-662-43948-7_80.