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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

Другой метод использует построение по индукции 3-связных графов для последовательного построения планарного вложения любой 3-связной компоненты графа G (а потому и планарного вложения самого графа G). Построение начинается с K₄ и определяется таким образом, что любой промежуточный граф на пути к полной компоненте является снова 3-связным. Поскольку такие графы имеют единственное вложение (с точностью до выбора внешней грани), следующий больший граф, если он остаётся планарным, должен быть уточнением предыдущего графа. Это позволяет свести проверку планарности к просто проверке, будет ли следующее добавленное ребро иметь оба конца на внешней грани текущего вложения. Будучи концептуально очень простым (и он даёт линейное время работы), метод обладает большой сложностью поиска последовательности построения.