Перевірка планарності

Задача перевірки планарності — це алгоритмічна задача перевірки, чи є даний граф планарним (тобто, чи можна його намалювати на площині без перетину ребер). Задачу добре вивчено в інформатиці і придумано багато практичних алгоритмів, зокрема, з використанням сучасних структур даних. Більшість цих методів працюють за час O(n) (лінійний час), де n — число ребер (або вершин) графа, що є асимптотично оптимальним алгоритмом^[en]. Замість простого булівського значення, вихід алгоритмів перевірки планарності може дати вкладення графа, якщо граф планарний, або заваду планарності, таку як підграф Куратовського, якщо граф не планарний.

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

Алгоритми перевірки планарності зазвичай користуються теоремами теорії графів, які описують множину планарних графів у термінах, що не залежать від малювання графів. Сюди входять

• Теорема Понтрягіна — Куратовського, що граф планарний тоді й лише тоді, коли він не містить підграфа, який є розбиттям K₅ (повного графа з п'ятьма вершинами) або K_3,3 (комунальний граф, повний двочастковий граф з шістьма вершинами, три з яких з'єднані з кожною вершиною з іншої трійки).
• Теорема Вагнера, що граф планарний тоді й лише тоді, коли він не містить мінора (підграфа стягувань), ізоморфного K₅ або K_3,3.
• Критерій планарності де Фрейсекса — Розенштіля^[en], що описує планарні графи в термінах упорядкування зліва направо в дереві пошуку в глибину.

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

Є й інші критерії планарності, які описують планарні графи математично, але які менш придатні для алгоритмів перевірки планарності:

• критерій планарності Вітні, що граф планарен тоді й лише тоді, коли його графовий матроїд^[en] є також кографовым;
• критерій планарності Маклейна, що описує планарні графи базисами їхніх циклічних просторів;
• теорема Шнайдера, що описує планарні графи порядковою розмірністю^[en] асоційованих частково впорядкованих множин;
• критерій планарності Колен де Вердьєра, що використовує спектральну теорію графів.

Алгоритм

Метод додавання шляху

Першим опублікованим (1974) алгоритмом перевірки планарності був класичний метод додавання шляху Гопкрофта і Тарджана^[1], який працював за лінійний час. Імплементацію алгоритму Гопкрофта і Тарджана включено до бібліотеки ефективних типів даних і алгоритмів^[en] Мельхорна, Муцель^[en] і Неера^[2][3][4]. 2012 року Тейлор^[5] розширив цей алгоритм для генерування всіх перестановок циклічних порядків ребер для вкладення двозв'язних компонент.

Метод додавання вершин

Методи додавання вершин полягає у створенні структури даних, що представляє можливі вкладення породженого підграфа даного графа, і додавання вершин по одній до цієї структури даних. Ці методи починалися з неефективного O(n²) методу, який 1967 року запропонували Лемпель, Івен^[en] і Цедербаум^[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] перебувають у відкритому доступі (мовою C++). Алгоритм, що визначає підграф Куратовського за лінійний від кількості вершин час, розробив Вільямсон у 1980-х роках^[18].

Метод послідовної побудови

Інший метод використовує побудову за індукцією 3-зв'язних графів для послідовної побудови планарного вкладення будь-якої 3-зв'язної компоненти графа G (а тому й планарного вкладення самого графа G)^[19]. Побудова починається з K₄ і визначається так, що будь-який проміжний граф на шляху до повної компоненти є знову 3-зв'язним. Оскільки такі графи мають єдине вкладення (з точністю до вибору зовнішньої грані), наступний більший граф, якщо він залишається планарним, має бути уточненням попереднього графа. Це дозволяє звести перевірку планарності до просто перевірки, чи буде наступне додане ребро мати обидва кінці на зовнішній грані поточного вкладення. Попри концептуальну простоту (і лінійний час роботи), метод має великьу складністю пошуку послідовності побудови.