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

Задача проверки планарности — это алгоритмическая задача проверки, является ли данный граф планарным (то есть, может ли он быть нарисован на плоскости без пересечения рёбер). Задача хорошо изучена в информатике и для неё было придумано много практических алгоритмов, многие из которых используют современные структуры данных. Большинство этих методов работают за время O(n) (линейное время), где n — число рёбер (или вершин) графа, что является асимптотически оптимальным алгоритмом^[англ.]. Вместо простого булевского значения, выход алгоритмов проверки планарности может дать вложение графа, если граф планарен, или преграду планарности, такую как подграф Куратовского, если граф не планарен.

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

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

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

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

Другие критерии планарности, которые описывают планарные графы математически, но которые меньше пригодны для алгоритмов проверки планарности, включают критерий планарности Уитни, что граф планарен тогда и только тогда, когда его графовый матроид является также кографовым, критерий планарности Маклейна, описывающий планарные графы базисами их циклических пространств, Теорема Шнайдера, описывающая планарные графы порядковой размерностью^[англ.] ассоциированных частично упорядоченных множеств, и критерий планарности Колен де Вердьера, использующий спектральную теорию графов.

Алгоритмы

Метод добавления пути

Первым опубликованным (в 1974 году) алгоритмом проверки планарности был классический метод добавления пути Хопкрофта и Тарьяна[1], который работал за линейное время. Имплементация алгоритма Хопкрофта и Тарьян включён в библиотеку эффективных типов данных и алгоритмов^[англ.] Мельхорна^[англ.], Муцеля^[англ.] и Неэра[2] [3][4]. В 2012, Тейлор[5] расширил этот алгоритм для генерации всех перестановок циклических порядков рёбер для вложения двусвязных компонент.

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

Метод добавления вершин путём создания структуры данных, представляющих возможные вложения порождённого подграфа данного графа и добавления вершин по одной к этой структуре данных. Эти методы начинались с неэффективного O(n^2) метода, предложенный Лемпелем, Ивеном^[англ.] и Цедербаумом в 1967[6]. Метод улучшили Ивен и Тарьян, которые нашли решение линейного времени для шага s,t-нумерации[7], а затем улучшили Бут и Люкер, разработавшие структуру данных PQ-дерева. С этими улучшениями метод стал линейным по времени и, на практике, стал работать быстрее метода добавления путей[8]. Этот метод был также расширен, чтобы эффективно вычислять планарное вложение (рисование) для планарных графов[9]. В 1999 году Ши и Сю упростили эти методы, используя PC-дерево (некорневой вариант PQ-дерева) и обход с отложенной выборкой дерева вершин с поиском в глубину[10].

Метод добавления рёбер

В 2004 году Бойер и Мирволд[11] разработали упрощённый алгоритм со временем работы O(n), который был навеян методом PQ-дерева, но в котором избавились от PQ-дерева и алгоритм использует добавление рёбер для вычисления планарного вложения, если такое возможно. В противном случае вычисляется подразделение Куратовского (либо графа K₅, либо графа K_3,3). Метод является одним из двух существующих в настоящее время алгоритмов (второй — алгоритм проверки планарности де Фрейсекса, де Мендеса и Розенштиля[12][13]). См. статью Бойера, Кортезе, Патригнами и Баттиста[14] с экспериментальным сравнением с предварительной версией алгоритма проверки планарности Бойера и Мирволда. При этом алгоритм проверки Бойера и Мирволда был расширен для выделения нескольких подразделений Куратовского непланарного входного графа со временем работы, линейно зависящим от размера выхода[15]. Исходники проверки планарности[16][17] и выделения нескольких подразделений Куратовского[16] находятся в открытом доступе (на языке C++). Алгоритм, определяющий подграф Куратовского за линейное от количества вершин время, разработал Вильямсон в 1980-х годах[18].

Метод последовательного построения

Другой метод использует построение по индукции 3-связных графов для последовательного построения планарного вложения любой 3-связной компоненты графа G (а потому и планарного вложения самого графа G)[19]. Построение начинается с 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  (неопр.). Дата обращения: 28 октября 2021. Архивировано 8 сентября 2008 года.
17. Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0  (неопр.). Дата обращения: 13 марта 2018. Архивировано 16 марта 2018 года.
18. Williamson, 1984, с. 681–693.
19. Schmidt, 2014, с. 967–978.

Литература

• John Hopcroft, Robert E. Tarjan. Efficient planarity testing // Journal of the Association for Computing Machinery. — 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 // Journal of Graph Algorithms and Applications. — 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. — (Lecture Notes in Computer Science).
• 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.