Доминирование рисунок является стилем графа рисунка из ориентированных ациклических графов , что делает достижимости отношения между вершинами визуально очевидным. В доминантности чертеже, вершины расположены в различных точках евклидовой плоскости и вершина v достижима из другой вершины U тогда и только тогда , когда обе декартовы координаты на V больше или равны координатам ц . Края основного рисунка могут быть нарисованы либо в виде отрезков прямых линий , либо, в некоторых случаях, в виде многоугольных цепочек . [1]
Планарные графики [ править ]
Каждый транзитивно редуцированный st -планарный граф , ориентированный ациклический планарный граф с одним источником и одним стоком, оба на внешней стороне некоторого вложения графа, имеют рисунок доминирования. Влево-вправо алгоритм для нахождения этих чертежей устанавливает е координаты каждой вершины будет его положение в поиске в глубине упорядочении графа, начиная с S и приоритезацией ребер справа налево порядка, и установив укоординаты должны быть получены таким же образом, но с приоритетом ребер слева направо. Типичные алгоритмы рисования с преобладанием включают в себя другую фазу уплотнения после этого назначения координат, смещение вершин вниз и влево, насколько это возможно, с сохранением свойств рисунка с преобладанием. Результирующий рисунок находится в целочисленной сетке n × n и отображает многие из симметрий основного топологического вложения. Этот рисунок и, в более общем смысле, любой рисунок доминирования транзитивно-редуцированного st -планарного графа обязательно является плоским, с прямыми краями. [1] [2]
Для st -планарных графов, которые не являются транзитивно редуцированными, эквивалентный транзитивно редуцированный граф может быть получен путем подразделения каждого ребра. Однако прямолинейный рисунок результирующего транзитивно сокращенного графа будет формировать рисунок исходного графа, в котором некоторые ребра имеют изгибы в фиктивных вершинах, введенных подразделением. [1] [2] Чертеж с преобладанием плоской поверхности не обязательно является направленным вверх плоским рисунком , потому что некоторые края могут быть горизонтальными, но поворот его на 45 ° обязательно дает плоский рисунок снизу вверх. [1] По сравнению с другими методами рисования ориентированных ациклических графиков, алгоритм слева-направо (вместе с этапом предварительной обработки планаризации) показал хорошие результаты с точки зрения площади создаваемых рисунков, количества изгибов и соотношения сторон. рисунка, но хуже по общей длине края. [3]
Непланарные графики [ править ]
Направленный ациклический граф (независимо от планарности) имеет рисунок доминирования тогда и только тогда, когда частично упорядоченный набор его вершин, упорядоченный по достижимости, имеет размерность два. Рисунок (повернутого) доминирования транзитивно редуцированного ориентированного ациклического графа может использоваться как диаграмма Хассе соответствующего частичного порядка. [4]
Кодоминирование [ править ]
Учитывая доминирующий рисунок направленного ациклического графа D 1 = ( V , E 1 ), инвертирование интерпретации одной оси приводит к новому отношению, которое можно было бы назвать сопоставимостью . Таким образом, точка ( x a , y a ) может считаться доступной из точки ( x b , y b ) всякий раз, когда x a ≥ x b, но y a ≤ y b . Таким образом, можно увидеть, что рисунок доминирования индуцирует второй направленный ациклический граф 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]
Ссылки [ править ]
- ^ a b c d Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), "4.7 доминирующие рисунки", рисование графиков: алгоритмы визуализации графиков , Прентис Холл , стр. 112–127, ISBN 978-0-13-301615-4.
- ^ а б Ди Баттиста, Джузеппе; Тамассия, Роберто ; Tollis, Иоаннис Г. (1992), "Площадь требование и отображение симметрии плоских вверх чертежей", Дискретная и вычислительная геометрия , 7 (4): 381-401, DOI : 10.1007 / BF02187850 , МР 1148953 .
- ^ Ди Баттиста, Джузеппе; Гарг, Ашим; Лиотта, Джузеппе; Паризе, Армандо; Тамассия, Роберто ; Тассинари, Эмануэле; Варджиу, Франческо; Висмара, Лука (2000), "направленный рисунок ациклические графы: экспериментальное исследование", Международный журнал вычислительной геометрии и приложений , 10 (6): 623-648, DOI : 10,1142 / S0218195900000358 , MR 1808215 .
- ^ Бейкер, KA; Фишберн, ПК ; Робертс, Ф.С. (1972), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
- ^ Таненбаум, Пол Дж .; Уайтсайдс, Сью (1996), "Одновременное доминирование представление нескольких ч.у.м." (PDF) , Order , 13 (4): 351-364, DOI : 10.1007 / bf00405594 , S2CID 121516733 .
- ^ Корнаропулос, Евгениос М .; Толлис, Иоаннис Г. (2013), «Рисунки слабого доминирования для ориентированных ациклических графов», в Didimo, Walter; Патриньяни, Маурицио (ред.), Рисование графиков: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Revised Selected Papers , Lecture Notes in Computer Science, 7704 , Springer, pp. 559–560 , DOI : 10.1007 / 978-3-642-36763-2_52.
