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