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

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