Алгоритм Хопкрофта-Тарьяна: Проверка планарности за линейное время

Алгоритм Хопкрофта-Тарьяна — один из самых сложных для понимания классических алгоритмов на графах. Он базируется на глубоком структурном анализе графа с помощью Поиска в глубину (DFS). При обходе DFS граф перестраивается в так называемое Пальмовое дерево (Palm Tree). Ребра графа делятся на "древесные" (по которым шел DFS) и "обратные" (которые ведут к уже посещенным предкам).

Фундамент алгоритма строится на вычислении функции Low(v) — самой "высокой" вершины (с наименьшим DFS-номером), до которой можно добраться из поддерева с корнем v, используя не более одного обратного ребра. Это позволяет разбить граф на Двусвязные компоненты (Блоки). По теореме, граф планарен тогда и только тогда, когда планарна каждая его двусвязная компонента.

Основная фаза алгоритма (Тест на вложимость) использует абстракцию путей (сегментов). Алгоритм пытается последовательно "встроить" каждый путь в плоскость.

Когда мы рисуем цикл на плоскости, он делит плоскость на две части: "внутри" цикла и "снаружи". Любой новый путь, который мы пытаемся добавить к этому циклу, должен быть нарисован либо полностью внутри, либо полностью снаружи. Если два новых пути имеют пересекающиеся концы на базовом цикле (интерферируют), они не могут быть уложены на одной стороне — один обязан лечь "внутри", а другой "снаружи".

Тарьян и Хопкрофт использовали структуру данных "Стек" для хранения текущих конфликтов (графа несовместимости сегментов). Алгоритм идет снизу вверх по DFS-дереву и решает 2-SAT задачу (выбор между левой и правой стороной для каждого пути). Если на каком-то этапе граф несовместимости требует поместить три конфликтующих сегмента по разные стороны от цикла (а сторон всего две), алгоритм немедленно останавливается и выдает вердикт: "Граф не планарен". Если DFS завершается успешно, граф гарантированно можно нарисовать без пересечений. Эта работа Тарьяна во многом определила стандарты современного асимптотического анализа.