Планарные графы и плоские рисунки

Свойство графа и свойство рисунка

Планарный граф можно нарисовать на плоскости так, чтобы рёбра встречались только в общих концах. Плоский граф — уже выбранное такое представление. Пересечение в одном неудачном рисунке не доказывает непланарности: рёбра можно изогнуть или вершины переставить.

Области, на которые рисунок разделяет плоскость, называют гранями. Неограниченная внешняя область тоже считается гранью. Для связного конечного плоского графа число вершин минус число рёбер плюс число граней равно 2. Это формула Эйлера, не критерий эйлерова обхода.

Откуда берётся формула

Для дерева рёбер на единицу меньше вершин и грань одна. Если к связному плоскому рисунку добавлять рёбра внутри граней, не создавая пересечений, каждое новое ребро, замыкающее цикл, делит одну грань на две. Числа рёбер и граней растут вместе, поэтому разность сохраняется.

Для простого планарного графа с не менее чем тремя вершинами следует ограничение $|E|\le3|V|-6$. Оно быстро исключает слишком плотные графы, но прохождение этой проверки само по себе планарность не доказывает.

Три примера

1. У треугольника три вершины, три ребра и две грани — внутренняя и внешняя. Получаем $3-3+2=2$.
2. Квадрат с одной диагональю имеет четыре вершины, пять рёбер, две внутренние треугольные грани и внешнюю: $4-5+3=2$.
3. Полный граф на пяти вершинах имеет $\binom52=10$ рёбер. Для планарности требовалось бы не более $3\cdot5-6=9$. Значит он непланарен.

Осторожно с условиями

Для несвязного плоского графа с $c$ компонентами формула имеет вид $|V|-|E|+|F|=1+c$. Ограничение числа рёбер выше требует простоты: петли и повторные рёбра меняют оценку. Не называйте пересечение рёбер вершиной без изменения модели. Непланарность — невозможность любого правильного рисунка, а не неудобство текущей схемы.