Какой простейший полиномиальный алгоритм для PLANARITY?

Есть несколько алгоритмов, которые решают за полиномиальное время, можно ли построить график на плоскости или нет, даже многие с линейным временем выполнения. Тем не менее, я не смог найти очень простой алгоритм, который можно было бы легко и быстро объяснить в классе, и показал бы, что PLANARITY в P. Знаете ли вы какой-нибудь?

При необходимости вы можете использовать теорему Куратовского или Фэри, но не углубляться, как теорема о второстепенном графе. Также обратите внимание, что мне плевать на время выполнения, я просто хочу что-то полиномиальное.

Ниже приведены 3 лучших алгоритма, демонстрирующие компромисс между простотой и отсутствием глубокой теории.

Алгоритм 1. Используя это, мы можем проверить, содержит ли граф или как минор за полиномиальное время, мы получаем очень простой алгоритм с использованием глубокой теории. (Обратите внимание, что эта теория уже использует вложения графа, как указал Саид, так что это не настоящий алгоритмический подход, просто что-то простое, чтобы сказать студентам, которые уже знали / приняли теорему о второстепенном графе.)К 3 , $K_5$$K_{3,3}$

Алгоритм 2 [на основе чьего-либо ответа]: легко понять, что достаточно иметь дело с 3-связными графами. Для этого найдите лицо, а затем примените весеннюю теорему Тутте.

Алгоритм 3 [рекомендовано Юхо]: алгоритм Демокрона, Мальгранжа и Пертуазе (DMP). Рисуем цикл, компоненты оставшегося графа называются фрагментами, мы их встраиваем подходящим образом (пока создаем новые фрагменты). Этот подход не использует никаких других теорем.

Я собираюсь описать алгоритм. Я не уверен, что это квалифицируется как «легкое», и некоторые доказательства не так просты.

Сначала мы разбиваем график на 3-связные компоненты, как упомянуто Чандрой Чекури.

1. Разбейте график на связанные компоненты.
2. Разбейте каждый подключенный компонент на 2 подключенных компонента. Это можно сделать в полиномиальной проверке времени для каждой вершины каждого 2-связного компонента , подключен ли .G i G i - $v$$G_i$$G_i-v$
3. Разбейте каждый 2-компонентный компонент на 3-компонентный. Это можно сделать при проверке за полиномиальное время для двух различных вершин каждого 2-связного компонента , связан ли .G i G i - { v , u $v,u$$G_i$$G_i-\{ v,u \}$

Мы сократили задачу до проверки, является ли трехсвязная компонента графа плоской. Пусть обозначает 3-связную компоненту.$G$

1. Возьмите любой цикл из .$C$$G$
2. Прикрепите вершины как вершины выпуклого многоугольника. Поместите каждую из остальных вершин в барицентр своих соседей. Это приводит к системе линейных уравнений, сообщающих координаты каждой вершины. Пусть будет результирующим рисунком; это может иметь пересечения.$C$$D$
3. Если не имеет пересечений, мы закончили.$D$
4. Возьмем вершины в любом связном компоненте группы . Ограничение на индуцированный подграф должно быть плоским. В противном случае не является плоской. Возьмем любое лицо на чертеже ограничивается индуцированного подграфа , и пусть будет цикл определение . Если должен быть плоским, то должен быть лицевым циклом. (Когда является гамильтоновым циклом, тогда должен быть построен с использованием ребра.)G - V ( C ) D G [ U ∪ V ( C ) ] G F D G [ U ∪ V ( C ) ] C ′ F G C ′ C C $U$$G-V(C)$$D$$G[U\cup V(C)]$$G$$F$$D$$G[U\cup V(C)]$$C'$$F$$G$$C'$$C$$C'$
5. Повторите шаг 2 с C 'вместо C. Если полученный чертеж плоский, то плоский. Остальное не плоское.$G$$G$

Примечания:

• Утверждать, что пружинное вложение Тутте дает плоское вложение, не просто. Мне понравилась презентация в книге Эдельсбруннера и Харера «Вычислительная топология», но она только для триангуляций. Колин де Вердиер обсуждает встраивание весны в http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , раздел 1.4. Общая ссылка - это Linial, Lovász, Wigderson: резиновые ленты, выпуклые вложения и связность графа. Combinatorica 8 (1): 91-102 (1988).
• Решение линейной системы уравнений в полиомном числе арифметических операций легко с помощью исключения Гаусса. Решить это, используя многозначное число битов, не так просто.

Алгоритм Бойера и Мирволда считается одним из самых современных алгоритмов тестирования планарности.

На переднем крае: упрощенная O (n) планарность путем сложения краев Бойера и Мирволда.

В этой главе книги рассматриваются многие алгоритмы тестирования на плоскостность, и, надеюсь, вы найдете достаточно простой алгоритм.

Как насчет алгоритма Хопкрофта и Тарьяна 1974 года {1} ?

{1} Хопкрофт, Джон и Роберт Тарьян. «Эффективное тестирование плоскостности». Журнал ACM (JACM) 21,4 (1974): 549-568.

Два алгоритма, оба в LogSpace

1. Эрик Аллендер и Мина Махаджан - Сложность тестирования планарности
2. Самир Датта и Гаутам Пракрия - повторное тестирование на плоскостность

Второе намного проще первого.