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

Эти графы тесно связаны с частично упорядоченными множествами и решётками. Диаграмма Хассе частично упорядоченного множества является ориентированным ациклическим графом, вершины которого являются множеством элементов, в котором есть ребро из x в y для каждой пары x, y элементов, для которых ${\displaystyle x\leqslant y}$ в частичном порядке, но для которого не существует z с ${\displaystyle x\leqslant y\leqslant z}$. Частично упорядоченное множество образует полную решётку тогда и только тогда, когда любое подмножество элементов имеет единственную наибольшую нижнюю границу и единственную наименьшую верхнюю границу, и порядковая размерность частично упорядоченного множества является наименьшим числом линейных упорядоченных множеств на том же самом множестве элементов, пересечение которых является данный частичный порядок. Если вершины st-планарного графа частично упорядочены по достижимости, то это упорядочение всегда формирует двухмерную полную решётку, диаграмма Хассе которой является транзитивным сокращением данного графа. Обратно Диаграмма Хассе любой двухмерной полной решётки является всегда st-планарным графом[2].

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