st-планарный граф

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

В рисунке каждая грань графа должна иметь ту же самую структуру — есть одна вершина, которая служит источником для грани, одна вершина служит стоком грани, а все рёбра внутри грани направлены вдоль двух путей от источника к стоку. Если нарисовать дополнительное ребро из стока st-планарного графа назад в источник по внешней грани и потом построить двойственный граф (ориентируя каждое двойственное ребро по часовой стрелке относительно исходного ребра), то получим снова st-планарный граф, расширенный дополнительным ребром тем же способомШаблон:R.

Теория порядков

Эти графы тесно связаны с частично упорядоченными множествами и решётками. Диаграмма Хассе частично упорядоченного множества является ориентированным ациклическим графом, вершины которого являются множеством элементов, в котором есть ребро из x в y для каждой пары x, y элементов, для которых $x⩽y$ в частичном порядке, но для которого не существует z с $x⩽y⩽z$. Частично упорядоченное множество образует полную решётку тогда и только тогда, когда любое подмножество элементов имеет единственную наибольшую нижнюю границу и единственную наименьшую верхнюю границу, и Шаблон:Не переведено 5 частично упорядоченного множества является наименьшим числом линейных упорядоченных множеств на том же самом множестве элементов, пересечение которых является данный частичный порядок. Если вершины st-планарного графа частично упорядочены по достижимости, то это упорядочение всегда формирует двухмерную полную решётку, диаграмма Хассе которой является транзитивным сокращением данного графа. Обратно Диаграмма Хассе любой двухмерной полной решётки является всегда st-планарным графомШаблон:R.

Рисование графов

Основываясь на этом свойстве двухмерного частичного порядка, любой st-планарный граф может быть представлен в виде Шаблон:Не переведено 5, в котором для каждых двух вершин u и v существует путь из u в v тогда и только тогда, когда обе координаты u меньше, чем соответствующие координаты vШаблон:Sfn. Координаты такого рисунка могут быть использованы в качестве структуры данных, которые могут быть использованы для проверки, что из вершины st-планарного графа можно достичь другую вершину за постоянное время на запрос. Поворот рисунка на 45° даёт восходящее планарное представление графа. Ориентированный ациклический граф G имеет восходящее планарное представление тогда и только тогда, когда G является подграфом st-планарного графаШаблон:R.