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

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

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

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

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

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

АлгоритмыПравить

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

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

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

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

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

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

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

Другой метод использует построение по индукции 3-связных графов для последовательного построения планарного вложения любой 3-связной компоненты графа G (а потому и планарного вложения самого графа G)[19]. Построение начинается с K4 и определяется таким образом, что любой промежуточный граф на пути к полной компоненте является снова 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. 1 2 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.

ЛитератураПравить

  • 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.