Рисунок доминирования
Рисование доминирования — это стиль рисования ориентированных ациклических графов , который делает отношения достижимости между вершинами визуально очевидными. При рисовании доминирования вершины размещаются в разных точках плоскости , и вершина 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 , yb , ) xa , ≥ xb Таким образом но ya ≤ если из ( .Таким образом, можно увидеть, что рисунок доминирования порождает второй ориентированный ациклический граф 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]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «4.7 Рисунки доминирования», Рисование графов: алгоритмы визуализации графов , Прентис Холл , стр. 112–127, ISBN 978-0-13-301615-4 .
- ^ Jump up to: а б Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1992), «Требования к площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (4): 381–401, doi : 10.1007/BF02187850 , MR 1148953 .
- ^ Ди Баттиста, Джузеппе; Гарг, Ашим; Лиотта, Джузеппе; Париз, Армандо; Тамассия, Роберто ; Тассинари, Эмануэле; Варджиу, Франческо; Висмара, Лука (2000), «Рисование ориентированных ациклических графов: экспериментальное исследование», Международный журнал вычислительной геометрии и приложений , 10 (6): 623–648, doi : 10.1142/S0218195900000358 , MR 1808215 .
- ^ Бейкер, Калифорния; Фишберн, ПК ; Робертс, Ф.С. (1972), «Частичные порядки размерности 2», Networks , 2 (1): 11–28, doi : 10.1002/net.3230020103 .
- ^ Таненбаум, Пол Дж.; Уайтсайдс, Сью (1996), «Одновременное доминантное представление нескольких частично упорядоченных наборов» (PDF) , Order , 13 (4): 351–364, doi : 10.1007/bf00405594 , S2CID 121516733 .
- ^ Корнаропулос, Евгениос М.; Толлис, Иоаннис Г. (2013), «Рисунки слабого доминирования для направленных ациклических графов», в Дидимо, Уолтер; Патриньяни, Маурицио (ред.), Рисование графиков: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7704, Springer, стр. 559–560, номер документа : 10.1007/978-3-642-36763-2_52 .