Проверка на планарность: различия между версиями

Задача заключается в установлении факта, является ли входной граф G планарным. Определение, наиболее подходящее для алгоритмов проверки на планарность, звучит так: граф G является планарным, если существует его вложение в плоскость (вершины G отображаются на различные точки, ребра G отображаются на кривые, соединяющие соответствующие конечные точки), такое, что ребра графа не пересекаются. Алгоритмы, проводящие проверку графа на планарность, можно модифицировать для получения подобного вложения.

 

Первый алгоритм с линейным временем исполнения предложили Хопкрофт и Тарьян [5], проанализировав итеративную версию рекурсивного алгоритма, разработанного Ауслендером и Партером [1] и модифицированного Голдштейном [4]. Алгоритм основывается на следующем наблюдении: связный граф является планарным в том и только том случае, если все его двусвязные компоненты являются планарными. Рекурсивный алгоритм последовательно обрабатывает каждую двусвязную компоненту: найти разделяющий цикл (separating cycle) C и разбиение ребер G, не принадлежащих C; определить компоненту разбиения как состоящую из ребер, связанных путем в G, и не включающую ребер из C; рекурсивно рассмотреть каждую циклическую компоненту разбиения. Если каждая компонента разбиения является планарной, а все компоненты могут быть объединены с C в планарный граф, то граф G является планарным.

Библиотека LEDA предлагает эффективную реализацию алгоритма Хопкрофта и Тарьяна [7]: http://www. algorithmic-solutions.info/leda_guide/graph_algorithms/ planar_kuratowski.html