В теории графов , й -planar график является биполярной ориентацией из плоского графа , для которого источник и приемник ориентации находится на внешней стороне графика. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что в графе нет направленных циклов, ровно одна вершина графа не имеет входящих ребер, ровно одна вершина графа не имеет исходящих ребер, и эти две обе специальные вершины лежат на внешней грани графа. [1]
На чертеже каждая грань графа должна иметь одинаковую структуру: есть одна вершина, которая действует как источник грани, одна вершина, которая действует как сток грани, и все ребра внутри грани направлены по двум путям. от истока до раковины. Если провести дополнительное ребро от стока st -планарного графа обратно к источнику через внешнюю грань, а затем построить двойственный граф (ориентированный каждое двойное ребро по часовой стрелке относительно его прямого ребра), то результатом снова будет st -планарный граф, дополненный таким же ребром. [1]
Теория порядка
Эти графы тесно связаны с частично упорядоченными множествами и решетками . Диаграмма Хассе частично упорядоченное множество представляет собой ориентированный ациклический граф, вершины которого являются набор элементов, с краем от й к у для каждой пару х , у элементов , для которых х ≤ у в частичном порядке , но для которых не существуют z с x ≤ y ≤ z . Частично упорядоченный набор образует полную решетку тогда и только тогда, когда каждое подмножество элементов имеет уникальную наибольшую нижнюю границу и уникальную наименьшую верхнюю границу, а размерность порядка частично упорядоченного набора - это наименьшее количество общих порядков на том же наборе элементов. элементы, пересечение которых является заданным частичным порядком. Если вершины st -планарного графа частично упорядочены по достижимости, то этот порядок всегда образует двумерную полную решетку, диаграмма Хассе которой является транзитивной редукцией данного графа. Наоборот, диаграмма Хассе каждой двумерной полной решетки всегда является st -планарным графом. [2]
Рисование графика
На основе этого двумерного свойства частичного порядка каждому st -планарному графу может быть дан рисунок доминирования , на котором для каждых двух вершин u и v существует путь от u к v тогда и только тогда, когда обе координаты u меньше, чем соответствующие координаты v . [3] Координаты такого чертежа также могут использоваться в качестве структуры данных, которая может использоваться для проверки того, может ли одна вершина st -planar графа достигнуть другой за постоянное время для каждого запроса. Поворот такого чертежа на 45 ° дает плоский рисунок графика вверх . Ориентированный ациклический граф G имеет плоский рисунок вверх тогда и только тогда, когда G является подграфом st -планарного графа. [4]
Рекомендации
- ^ а б Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «4.2 Свойства плоских ациклических орграфов», Graph Drawing: Algorithms for the Visualization of Graph , Prentice Hall , pp. 89–96, ISBN 978-0-13-301615-4.
- ^ Платт, CR (1976), "Плоские решетки и плоские графы", Журнал комбинаторной теории , сер. В, 21 (1): 30–39, DOI : 10.1016 / 0095-8956 (76) 90024-1.
- ^ Ди Баттиста и др. (1998) , 4.7 Рисунки доминирования, стр. 112–127.
- ^ Ди Баттиста, Джузеппе; Tamassia, Роберто (1988), "Алгоритмы для плоских представлений ациклических орграфов", Теоретическая информатика , 61 (2-3): 175-198, DOI : 10,1016 / 0304-3975 (88) 90123-5.