Планарные графы (часть 2)

  1. Поток в планарном графе.
  2. При укладке графа прямыми отрезками удобно сперва все его грани триангулировать (разбить на треугольники). Для этого в каждую не треугольную грань добавим фиктивную вершину.
  3. Как сделать граф трёхсвязным: триангулировать его
  4. Алгоритм укладки #1: Демукрон + Триангуляция + Татт + Удалить мусор
  5. Алгоритм укладки #2: физическое моделирование (вершины отталкиваются пропорционально 1/d2, притягиваются по ребру пропорционально d-1)
  6. Реклама. Алгоритмы за линейное время: алгоритм Тарьяна'1974
  7. Генерация планарных графов
    1. Бросаем случайные вершины на гриде, случайные прямые рёбра, проверяем, что нет пересечений
    2. Генерируем через рекурсивную триангуляцию, флипаем удаляем случайные рёбра
    3. Генерируем случайные прямые, строим пересечения
    4. Берём рёбра в случайном порядке, бинпоиском ищем max планарный префикс (внутри бинпоиска проверка Демукроном), на суффиксе рекурсивно.
    5. Добить граф до непланарного: добавить случайные рёбра, чтобы их было хотя бы 3V-5.
  8. Визуализация
    1. Картинка
    2. Физическая система (видео)
    3. Интерактивная (можно подёргать вершины)