Тестирование планарности

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

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

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

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

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

Другие критерии планарности, которые математически характеризуют планарные графы, но менее важны для алгоритмов тестирования планарности, включают:

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

Алгоритмы

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

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

Метод сложения вершин

Методы добавления вершин работают путем поддержания структуры данных, представляющей возможные вложения индуцированного подграфа данного графа, и добавления вершин по одной в эту структуру данных. Эти методы начались с неэффективного метода O( n2 ) ^, предложенного Лемпелем , Эвеном и Седербаумом в 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] общедоступен. Алгоритмы, позволяющие найти подграф Куратовского в вершинах за линейное время, были разработаны Уильямсоном в 1980-х годах. ^[18]

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

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

Динамические алгоритмы

Тестирование планарности изучалось в модели динамических алгоритмов , в которой сохраняется ответ на проблему (в данном случае планарность), поскольку граф подвергается локальным обновлениям, обычно в форме вставки/удаления ребер. В случае поступления ребра существует асимпотически точный алгоритм времени обновления обратной функции Аккермана , предложенный Ла Путре ^[20] и усовершенствовавший алгоритмы Ди Баттисты, Тамассиа и Уэстбрука. ^[21]^[22]^[23] В полностью динамическом случае, когда ребра одновременно вставляются и удаляются, существует логарифмическая нижняя граница времени обновления Патрашку и Демэна , ^[24] и полилогарифмический алгоритм времени обновления Холма и Ротенберг ^[25] усовершенствовал сублинейные алгоритмы времени обновления Эппштейна , Галила , Итальяно , Сарнака и Спенсера. ^[26]^[27]