Плоский рисунок вверх - Upward planar drawing

Плоский рисунок снизу вверх
Этот плоский DAG не имеет восходящего рисунка, потому что его источник и приемник не могут находиться на одной грани.

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

Характеристики

Ориентированный ациклический граф должен быть планарный чтобы иметь восходящий планарный рисунок, но не каждый плоский ациклический граф имеет такой рисунок. Среди плоских ориентированных ациклических графов с одним источником (вершина без входящих ребер) и стоком (вершина без исходящих ребер) графы с направленными вверх плоскими рисунками являются ул-плоские графы, планарные графы, в которых источник и сток принадлежат одной и той же грани хотя бы одного из плоских вложений графа. В более общем плане график грамм имеет восходящий плоский рисунок тогда и только тогда, когда он направлен и ацикличен, и является подграфом ул-планарный граф на том же множестве вершин.[2]

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

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

Вычислительная сложность

Известно, что несколько частных случаев тестирования восходящей планарности возможны в полиномиальное время:

  • Проверка того, является ли график ул-планарный может быть выполнен в линейное время добавив ребро из s к т и проверка того, является ли оставшийся граф плоским. Аналогичным образом можно построить восходящий плоский рисунок (если он существует) ориентированного ациклического графа с одним источником и стоком за линейное время.[5]
  • Проверка того, может ли ориентированный граф с фиксированным планарным вложением быть нарисованным вверх плоским, с вложением, согласованным с данным, может быть выполнено путем проверки того, что вложение является бимодальным, и моделирования проблемы согласованного назначения как сетевой поток проблема. Время работы линейно зависит от размера входного графа и полиномиально от количества источников и приемников.[6]
  • Потому что ориентирован многогранные графы имеют уникальное плоское вложение, наличие восходящего плоского рисунка для этих графов может быть проверено за полиномиальное время.[7]
  • Проверка того, внешнепланарный ориентированный ациклический граф имеет направленный вверх плоский рисунок, также полиномиальный.[8]
  • Каждый последовательно-параллельный граф, ориентированная согласованно с последовательно-параллельной структурой, плоская вверх. Планарный рисунок вверх может быть построен непосредственно из последовательно-параллельной декомпозиции графа.[9] В общем, произвольный ориентации неориентированных последовательно-параллельных графов можно проверить на планарность вверх за полиномиальное время.[10]
  • Каждый ориентированное дерево направлено вверх.[9]
  • Каждый двудольный плоский граф, чьи ребра ориентированы последовательно от одной стороны двудольного деления к другой, является планарным вверх[9][11]
  • Известен более сложный алгоритм полиномиального времени для проверки восходящей планарности графов, имеющих один источник, но несколько приемников, или наоборот.[12]
  • Тестирование восходящей планарности может быть выполнено за полиномиальное время, когда имеется постоянное количество трехсвязных компонентов и вырезанных вершин, и управляемый с фиксированными параметрами в этих двух числах.[13] Он также является управляемым с фиксированными параметрами в цикломатическое число входного графа.[14]
  • Если у-координаты всех вершин фиксированы, тогда выбор Икс-координаты, которые делают рисунок вверх плоским, могут быть найдены за полиномиальное время.[15]

Однако это НП-полный чтобы определить, имеет ли планарно направленный ациклический граф с несколькими источниками и стоками направленный вверх плоский рисунок.[16]

Прямолинейный рисунок и требования к площади

Теорема Фари утверждает, что у каждого плоского графа есть рисунок, на котором его ребра представлены отрезками прямых линий, и то же самое верно для восходящего плоского рисунка: каждый восходящий плоский граф имеет прямой восходящий плоский рисунок.[17]Прямолинейный рисунок снизу вверх транзитивно сокращенный ул-планарный граф может быть получен методом рисунок доминирования, причем все вершины имеют целочисленные координаты в пределах п × п сетка.[18] Однако для некоторых других восходящих планарных графов может потребоваться экспоненциальный площадь на всех их прямолинейных, направленных вверх плоских рисунках.[17] Если выбор вложения фиксирован, даже ориентированные последовательные параллельные графы и ориентированные деревья могут потребовать экспоненциальной площади.[19]

Диаграммы Хассе

Плоские чертежи вверх особенно важны для Диаграммы Хассе из частично упорядоченные наборы, так как эти диаграммы обычно необходимо рисовать вверх. В терминах теории графов они соответствуют транзитивно сокращенный ориентированные ациклические графы; такой граф может быть сформирован из покрывающего отношения частичного порядка, а сам частичный порядок образует достижимость отношение в графе. Если частично упорядоченный набор имеет один минимальный элемент, один максимальный элемент и имеет направленный вверх плоский рисунок, то он обязательно должен образовывать решетка, множество, в котором каждая пара элементов имеет единственную точную нижнюю границу и единственную точную верхнюю границу.[20] Диаграмма Хассе решетки плоская тогда и только тогда, когда ее размер заказа не больше двух.[21] Однако некоторые частичные порядки размерности два и с одним минимальным и максимальным элементом не имеют направленного вверх плоского рисунка (возьмите порядок, определенный транзитивным замыканием ).

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

Сноски
  1. ^ Гарг и Тамассия (1995); Di Battista et al. (1998).
  2. ^ Гарг и Тамассия (1995), стр. 111–112; Di Battista et al. (1998), 6.1 "Включение в плоский ул-Граф », с. 172–179; Ди Баттиста и Тамассия (1988); Келли (1987).
  3. ^ Гарг и Тамассия (1995), стр. 112–115; Di Battista et al. (1998), 6.2 «Углы на чертежах вверх», стр. 180–188; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994).
  4. ^ Гарг и Тамассия (1995), п. 115; Di Battista et al. (1998), 6.7.2 «Запрещенные циклы для одноисточников орграфов», стр. 209–210; Томассен (1989).
  5. ^ Гарг и Тамассия (1995), п. 119; Di Battista et al. (1998), п. 179.
  6. ^ Гарг и Тамассия (1995), стр. 119–121; Di Battista et al. (1998), 6.3 «Тестирование встроенных орграфов вверх на планарность», стр. 188–192; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994); Аббаси, Хили и Рекстин (2010).
  7. ^ Di Battista et al. (1998), стр. 191–192; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994).
  8. ^ Гарг и Тамассия (1995), стр. 125–126; Di Battista et al. (1998), 6.7.1 «Внешнепланарный орграф», с. 209; Папакостас (1995).
  9. ^ а б c Di Battista et al. (1998), 6.7.4 «Некоторые классы восходящих плоских орграфов», с. 212.
  10. ^ Дидимо, Джордано и Лиотта (2009).
  11. ^ Ди Баттиста, Лю и соперник (1990).
  12. ^ Гарг и Тамассия (1995), стр. 122–125; Di Battista et al. (1998), 6.5 «Тестирование оптимальной восходящей планарности орграфов с одним источником», стр. 195–200; Хаттон и Любив (1996); Бертолацци и др. (1998).
  13. ^ Чан (2004); Хили и Линч (2006).
  14. ^ Хили и Линч (2006).
  15. ^ Юнгер и Лейперт (1999).
  16. ^ Гарг и Тамассия (1995), стр. 126–132; Di Battista et al. (1998), 6.6 «Тестирование восходящей планарности NP-завершено», стр. 201–209; Гарг и Тамассия (2001).
  17. ^ а б Ди Баттиста и Фрати (2012); Ди Баттиста, Тамассия и Толлис (1992).
  18. ^ Di Battista et al. (1998), 4.7 «Рисунки доминирования», стр. 112–127; Ди Баттиста, Тамассия и Толлис (1992).
  19. ^ Ди Баттиста и Фрати (2012); Бертолацци и др. (1994); Фрати (2008).
  20. ^ Di Battista et al. (1998), 6.7.3 «Запрещенные конструкции для решеток», стр. 210–212; Платт (1976).
  21. ^ Гарг и Тамассия (1995), pp. 118; Бейкер, Фишберн и Робертс (1972).
Обзоры и учебники
  • Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), «Поток и восходящая планарность», Рисование графиков: алгоритмы визуализации графиков, Prentice Hall, стр. 171–213, ISBN  978-0-13-301615-4.
  • Ди Баттиста, Джузеппе; Фрати, Фабрицио (2012), «Рисование деревьев, внешнепланарных графов, последовательно-параллельных графов и плоских графов на небольшой площади», Тридцать очерков по теории геометрических графов, Алгоритмы и комбинаторика, 29, Springer, стр. 121–165, Дои:10.1007/978-1-4614-0110-0_9, ISBN  9781461401100. Раздел 5, «Рисунки снизу вверх», стр. 149–151.
  • Гарг, Ашим; Тамассия, Роберто (1995), "Тестирование восходящей планарности", Заказ, 12 (2): 109–133, Дои:10.1007 / BF01108622, МИСТЕР  1354797.
Исследовательские статьи