Рисунок доминирования - Dominance drawing

Рисунок доминирования

Рисунок доминирования это стиль рисунок графика из ориентированные ациклические графы что делает достижимость отношения между вершинами визуально очевидны. В чертеже с преобладанием вершины расположены в различных точках Евклидова плоскость и вершина v достижимо из другой вершины ты если и только если оба Декартовы координаты из v больше или равны координатам ты. Края рисунка с преобладанием могут быть нарисованы как прямые. отрезки линии, или, в некоторых случаях, как многоугольные цепи.[1]

Планарные графики

Каждый транзитивно сокращенный ул-планарный граф, направленный ациклический планарный граф с одним источником и одним стоком, оба на внешней стороне некоторого вложения графа, имеют рисунок доминирования. В лево-правый алгоритм для поиска этих рисунков устанавливает Икс координата каждой вершины, чтобы быть ее положением в поиск в глубину упорядочение графика, начиная с s и приоритезация краев в порядке справа налево, а также установив у координаты должны быть получены таким же образом, но с приоритетом ребер слева направо. Типичные алгоритмы рисования с преобладанием включают в себя еще одну фазу уплотнения после этого назначения координат, смещение вершин вниз и влево, насколько это возможно, с сохранением свойств рисунка с преобладанием. Полученный рисунок находится внутри п × п целочисленная сетка, и отображает многие из симметрий основного топологического вложения. Этот рисунок, и, в более общем плане, каждый рисунок преобладания переходно-сокращенной ул-планарный граф, обязательно плоский, с прямыми ребрами.[1][2]

За ул-планарных графов, которые не являются транзитивно редуцированными, эквивалентный транзитивно редуцированный граф может быть получен подразделение каждый край. Однако прямая линия результирующего транзитивно сокращенного графа будет формировать рисунок исходного графа, в котором некоторые ребра имеют изгибы, в фиктивных вершинах, введенных делением.[1][2] Чертеж плоского доминирования не обязательно направленный вверх плоский рисунок, потому что некоторые кромки могут быть горизонтальными, но поворот на 45 ° обязательно дает плоский рисунок вверх.[1] По сравнению с другими методами рисования ориентированных ациклических графов, алгоритм слева направо (вместе с этапом предварительной обработки планаризации) показал хорошие результаты с точки зрения площадь чертежей, которые он производит, количество изгибов и соотношение сторон рисунка, но хуже по общей длине края.[3]

Непланарные графы

Направленный ациклический граф (независимо от планарности) имеет рисунок доминирования тогда и только тогда, когда частично заказанный набор вершин, упорядоченных по достижимости, имеет размер заказа два. Рисунок (повернутого) преобладания транзитивно редуцированного ориентированного ациклического графа может использоваться как Диаграмма Хассе соответствующего частичного порядка.[4]

Кодоминантность

Учитывая доминирующий рисунок ориентированного ациклического графа D1 = (V, E1), инвертирование интерпретации одной оси приводит к новому отношению, которое можно назвать доступностьТаким образом, точка (Икса, уа) можно считать доступным с точки (Иксб, уб) в любое время Икса ≥ Иксб но уа ≤ убТаким образом, можно увидеть, что рисунок доминирования индуцирует второй направленный ациклический граф. D2 = (V, E2) на одном и том же множестве вершин. Пары {≤1, ≤2} частичных заказов на общем наземном комплексе, которые позволяют такое одновременное представление в виде одного рисунка, интерпретируемого с точки зрения достижимости и доступности, называются содоминантный.[5]

Рисунок слабого доминирования

Для ориентированных ациклических графов, порядок достижимости которых имеет более высокую размерность, a рисунок слабого доминирования - это рисунок, на котором каждое ребро ориентировано вверх, вправо или и то, и другое, но на котором существуют пары вершин (ты, v) для которого ты доминирует v покоординатно, но v недоступен из ты в графике. Мы сказали, что вершина ты доминирует над другой вершиной v если координаты (u_x, u_y) ты меньше или равны координатам (v_x, v_y) v, т.е. u_x <= v_x и u_y <= v_y с учетом плоскости XY. Цель этого стиля рисования - минимизировать количество таких ложно подразумеваемые пути.[6]

Рекомендации

  1. ^ а б c d Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), "4.7 Рисунки доминирования", Рисование графиков: алгоритмы визуализации графиков, Prentice Hall, стр. 112–127, ISBN  978-0-13-301615-4.
  2. ^ а б Ди Баттиста, Джузеппе; Тамассия, Роберто; Толлис, Иоаннис Г. (1992), «Требуемая площадь и отображение симметрии плоских восходящих чертежей», Дискретная и вычислительная геометрия, 7 (4): 381–401, Дои:10.1007 / BF02187850, МИСТЕР  1148953.
  3. ^ Ди Баттиста, Джузеппе; Гарг, Ашим; Лиотта, Джузеппе; Паризе, Армандо; Тамассия, Роберто; Тассинари, Эмануэле; Варджиу, Франческо; Висмара, Лука (2000), «Рисование направленных ациклических графиков: экспериментальное исследование», Международный журнал вычислительной геометрии и приложений, 10 (6): 623–648, Дои:10.1142 / S0218195900000358, МИСТЕР  1808215.
  4. ^ Бейкер, К. А .; Фишберн, П.С.; Робертс, Ф.С. (1972), «Частичные порядки размерности 2», Сети, 2 (1): 11–28, Дои:10.1002 / нетто.3230020103.
  5. ^ Таненбаум, Пол Дж .; Уайтсайдс, Сью (1996), «Одновременное доминирование нескольких позы» (PDF), Заказ, 13 (4): 351–364, Дои:10.1007 / bf00405594, S2CID  121516733.
  6. ^ Корнаропулос, Евгениос М .; Толлис, Иоаннис Г. (2013), «Рисунки слабого доминирования для ориентированных ациклических графов», в Didimo, Walter; Патриньяни, Маурицио (ред.), Графический рисунок: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19-21 сентября 2012 г., Пересмотренные избранные статьи, Конспект лекций по информатике, 7704, Springer, стр. 559–560, Дои:10.1007/978-3-642-36763-2_52.