Планарные графы (1 ноября 2016)

  1. [20 минут] Определения, теоремы
    1. Планарный граф, плоский граф
    2. Укладка на плоскости − то же, что и укладка на сфере. Любую грань можно сделать внешней.
    3. Теорема Эйлера. E+K+1=V+G. Следствие. E ≤ 3V-6. Док-во: у каждой грани хотя бы 3 ребра. Поэтому E ≥ 1.5*G...
    4. Алгоритмическое следствие: во всех алгоритмах на планарных графах E = O(V).
    5. Теорема Куратовского [1930]: граф планарен iff, не содержит подграфов гомеоморфных K3,3 или K5
    6. Теорема Вагнера (аналог Куратовского) [1937]: граф планарен iff, не содержит подграфов стягиваемых к K3,3 или K5.
    7. Пример с K5 с раздвоенной вершиной (Вагнер и Куратовский − не одно и то же: Вагнер видит K5, Куратовский K3,3)
    8. Теорема Фари [1948]: любой планарный граф можно уложить с использованием только прямых отрезков.
    9. [skipped] Теорема Фари: доказательство по индукции.
    10. Schnyder [1989]: любой планарный граф при V ≥ 3 можно уложить с использованием только прямых отрезков на гриде размера (V-2)×(V-2). Укладку можно найти за O(V).
  2. [5 минут] Алгоритмы укладки
    1. Demoucron [1964], O(n2)
    2. Tarjan, Hopcroft [1974], O(n)
    3. Simply O(n): Ulrik Brandes [2011]; LR-Planarity-Testing; Boyer and Myrvold [2004]
    4. Tutte Spring Theorem [1963]: любой трёхсвязный планарный граф однозначно укладывается на плоскость таким образом, что каждая его грань, включая внешнюю, − выпуклый многоугольник, а любая внутренняя вершина − центр масс соседей.
  3. [10 минут] Tutte Spring Theorem
    1. Делаем граф трёхсвязным и триангулируем его
    2. Алгоритм укладки: уложить как угодно внешнюю грань, любая другая вершина лежит в центре масс соседей.
    3. Убираем лишние рёбра
    4. Гаусс и метод итерации для решения систем линейных уравнений.
  4. [30 минут] Алгоритм Демукрона
    1. Нарисовали цикл, выделили компоненты, укладываем компоненты независимо
    2. Укладка компоненты с внешним циклом: нарисовали любой путь путь, разбили цикл на два, компоненту на подкомпоненты, рекурсивно вызвались
  5. [skipped] [10 минут] Алгоритм выделение граней плоского графа
    1. [skipped] Данные: xi, yi, edges
    2. [skipped] Алгоритм за O(n): храним для каждого ребра next и reversed, dfs по непосещённым рёбрам
    3. [skipped] Внешняя грань