Рисование доминирования — это стиль рисования ориентированных ациклических графов , который делает отношения достижимости между вершинами визуально очевидными. При рисовании доминирования вершины размещаются в разных точках евклидовой плоскости , и вершина v достижима из другой вершины u тогда и только тогда, когда обе декартовы координаты v больше или равны координатам u . Края рисунка доминирования могут быть нарисованы либо в виде отрезков прямых линий , либо, в некоторых случаях, в виде многоугольных цепочек . [1]
Каждый транзитивно редуцированный st -планарный граф , направленный ациклический планарный граф с одним источником и одним стоком, оба на внешней грани некоторого вложения графа, имеет рисунок доминирования. Алгоритм слева-справа для поиска этих рисунков устанавливает координату x каждой вершины в качестве ее позиции в порядке поиска в глубину графа, начиная с s и расставляя приоритеты ребер в порядке справа налево, а также устанавливая y Координата должна быть получена таким же способом, но с приоритетом ребер в порядке слева направо. Типичные алгоритмы рисования доминирования включают в себя еще одну фазу уплотнения после присвоения координат, сдвигая вершины вниз и влево, насколько это возможно, сохраняя при этом свойства рисунка доминирования. Полученный рисунок находится внутри целочисленной сетки размера n × n и отображает многие симметрии лежащего в основе топологического вложения. Этот рисунок и, в более общем смысле, каждый рисунок доминирования транзитивно редуцированного st -планарного графа обязательно является плоским, с прямыми краями. [1] [2]
Для st -планарных графов, которые не являются транзитивно редуцируемыми, эквивалентный транзитивно редуцированный граф может быть получен путем разделения каждого ребра. Однако прямолинейный рисунок результирующего транзитивно редуцированного графа будет образовывать рисунок исходного графа, в котором некоторые ребра имеют изгибы в фиктивных вершинах, введенных подразделением. [1] [2] Плоский доминантный рисунок не обязательно является плоским рисунком, направленным вверх , поскольку некоторые края могут быть горизонтальными, но поворот его на 45 ° обязательно дает плоский рисунок, направленный вверх. [1] По сравнению с другими методами рисования ориентированных ациклических графов алгоритм «лево-право» (вместе с этапом предварительной обработки планаризации) показал хорошие результаты с точки зрения площади создаваемых рисунков, количества изгибов и соотношение сторон рисунка, но хуже по общей длине края. [3]
Ориентированный ациклический граф (независимо от планарности) имеет рисунок доминирования тогда и только тогда, когда частично упорядоченное множество его вершин, упорядоченное по достижимости, имеет размерность порядка два. (Повернутый) рисунок доминирования транзитивно редуцированного ориентированного ациклического графа может использоваться как диаграмма Хассе соответствующего частичного порядка. [4]
Учитывая рисунок доминирования ориентированного ациклического графа D 1 = ( V , E 1 ), инвертирование интерпретации одной оси приводит к новому отношению, которое можно было бы назвать достижимостью . Таким образом , точку ( xa , ya ) можно считать достижимой из точки ( xb , yb ) , если xa ≥ xb , но ya ≤ yb . Таким образом, можно увидеть, что рисунок доминирования порождает второй ориентированный ациклический граф D 2 = ( V , E 2 ) на том же множестве вершин. Пары {≤ 1 , ≤ 2 } частичных порядков на общем множестве оснований, которые допускают такое одновременное представление одним рисунком, интерпретируемым с точки зрения достижимости и содостижимости, называются кодоминантными. [5]
Для ориентированных ациклических графов, порядок достижимости которых имеет более высокую размерность, рисунок со слабым доминированием — это рисунок, в котором каждое ребро ориентировано вверх, вправо или и то, и другое, но в котором существуют пары вершин ( u , v ), для которых u доминирует над v по координатам. но v недоступен из u в графе. Мы сказали, что вершина u доминирует над другой вершиной v , если координаты (u_x, u_y) u меньше или равны координатам (v_x, v_y) v , т. е. u_x <= v_x и u_y <= v_y, учитывая плоскость XY. . Целью этого стиля рисования является минимизация количества таких ложно подразумеваемых путей . [6]