Планарные графы
- Определение: планарный граф, плоский граф
- Укладка на плоскости − то же, что и укладка на сфере. Любую грань можно сделать внешней.
- Теорема Эйлера. E+K+1=V+G. Следствие. E ≤ 3V-6. Док-во: у каждой грани хотя бы 3 ребра. Поэтому E ≥ 1.5*G...
- Следствие: во всех алгоритмах на планарных графах E = O(V), поэтому алгоритм работающий за O(f(E)) работает за O(f(V))
- Теорема Куратовского [1930]: граф планарен iff, не содержит подграфов гомеоморфных K3,3 или K5
- Теорема Вагнера (аналог Куратовского) [1937]: граф планарен iff, не содержит подграфов стягиваемых к K3,3 или K5. Пример с K5 с раздвоенной вершиной (Вагнер и Куратовский − не одно и то же)
- Теорема Фари [1948]: любой планарный граф можно уложить с использованием только прямых отрезков
- Шнайдер [1989]: любой планарный граф можно уложить с использованием только прямых отрезков на гриде размера (V-2)×(V-2). Укладку можно найти за O(V).
- Татт [1963]: любой трёхсвязный планарный граф однозначно укладывается на плоскость таким образом, что каждая его грань, включая внешнюю, − выпуклый многоугольник, а любая внутренняя вершина − центр масс соседей.
- Гаусс. Физическая система для укладки трёхсвязных графов. Метод итерации для решения систем линейных уравнений.
- Алгоритм Демукрона, две версии (раскраска в два цвета vs события). Получение укладки за O(V2).