Планарные графы

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