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

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

Метод добавления вершин путём создания структуры данных, представляющих возможные вложения порождённого подграфа данного графа и добавления вершин по одной к этой структуре данных. Эти методы начинались с неэффективного O(n²) метода, предложенный Лемпелем, Ивеном и Цедербаумом в 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-связным. Поскольку такие графы имеют единственное вложение (с точностью до выбора внешней грани), следующий больший граф, если он остаётся планарным, должен быть уточнением предыдущего графа. Это позволяет свести проверку планарности к просто проверке, будет ли следующее добавленное ребро иметь оба конца на внешней грани текущего вложения. Будучи концептуально очень простым (и он даёт линейное время работы), метод обладает большой сложностью поиска последовательности построения.