Граф с ребрами, непересекающимися и направленными вверх
Плоский рисунок вверхЭтот плоский DAG не имеет направленности вверх, поскольку его источник и приемник не могут находиться на одной грани.
В рисовании графа плоское рисование направленного ациклического графа вверх представляет собой вложение графа в евклидову плоскость , в которой ребра представлены как непересекающиеся монотонные направленные вверх кривые. То есть кривая, представляющая каждое ребро, должна обладать свойством, согласно которому каждая горизонтальная линия пересекает ее не более чем в одной точке, и никакие два ребра не могут пересекаться, кроме как в общей конечной точке. [1] В этом смысле это идеальный случай для рисования многослойных графов , стиля рисования графа, в котором ребра представляют собой монотонные кривые, которые могут пересекаться, но в котором пересечения должны быть минимизированы.
Характеристики
Направленный ациклический граф должен быть планарным , чтобы иметь планарный рисунок вверх, но не каждый планарный ациклический граф имеет такой рисунок. Среди планарных направленных ациклических графов с одним источником (вершина без входящих ребер) и стоком (вершина без выходящих ребер) графы с планарными рисунками вверх являются st - планарными графами , планарными графами, в которых принадлежат как источник, так и сток. к одной и той же грани хотя бы одного из плоских вложений графа. В более общем смысле, граф G имеет планарный рисунок вверх тогда и только тогда, когда он направлен и ацикличен и является подграфом st -планарного графа на том же множестве вершин. [2]
При вложении вверх множества входящих и исходящих ребер, инцидентных каждой вершине, смежны в циклическом порядке ребер в вершине. Планарное вложение заданного ориентированного ациклического графа называется бимодальным, если оно обладает этим свойством. Кроме того, угол между двумя последовательными ребрами с одинаковой ориентацией в данной вершине может быть помечен как малый , если он меньше π, или большой , если он больше π. Каждый источник или сток должен иметь ровно один большой угол, а каждая вершина, которая не является ни источником, ни стоком, не должна иметь ни одного угла. При этом каждая внутренняя грань чертежа должна иметь на два малых угла больше, чем больших, а внешняя грань должна иметь на два больших угла больше, чем малых. Непротиворечивое присвоение — это маркировка углов, удовлетворяющая этим свойствам; каждое восходящее вложение имеет последовательное назначение. И наоборот, каждый направленный ациклический граф, имеющий бимодальное плоское вложение с непротиворечивым присваиванием, имеет планарный рисунок, направленный вверх, который можно построить на его основе за линейное время. [3]
Другая характеристика возможна для графов с одним источником. В этом случае плоское вложение вверх должно иметь источник на внешней грани, и каждый неориентированный цикл графа должен иметь хотя бы одну вершину, в которую входят оба ребра цикла (например, вершина с самым высоким расположением на чертеже). . И наоборот, если вложение обладает обоими этими свойствами, то оно эквивалентно вложению вверх. [4]
Вычислительная сложность
Известно, что за полиномиальное время возможны несколько особых случаев проверки восходящей планарности :
Проверка того, является ли граф st -планарным, может быть выполнена за линейное время путем добавления ребра от s до t и проверки того, является ли оставшийся граф плоским. Аналогичным образом можно построить восходящий планарный рисунок (если он существует) ориентированного ациклического графа с одним источником и стоком за линейное время. [5]
Проверка того, может ли ориентированный граф с фиксированным плоским вложением быть нарисован восходящим плоским, с вложением, соответствующим заданному, может быть достигнута путем проверки того, что вложение является бимодальным, и моделирования задачи согласованного назначения как задачи сетевого потока . Время работы линейно зависит от размера входного графа и полиномиально от количества источников и приемников. [6]
Поскольку ориентированные многогранные графы имеют уникальное планарное вложение, существование плоского рисунка вверх для этих графов можно проверить за полиномиальное время. [7]
Проверка того, имеет ли внешнепланарно -направленный ациклический граф планарный рисунок вверх, также является полиномиальным. [8]
Каждый последовательно-параллельный граф , ориентированный последовательно с последовательно-параллельной структурой, является восходящим планарным. Планарный рисунок вверх можно построить непосредственно на основе последовательно-параллельного разложения графа. [9] В более общем смысле, произвольные ориентации неориентированных последовательно-параллельных графов могут быть проверены на предмет планарности вверх за полиномиальное время. [10]
Каждый двудольный планарный граф, ребра которого последовательно ориентированы от одной стороны двудольного деления к другой, является планарным снизу вверх [9] [11]
Известен более сложный алгоритм с полиномиальным временем для проверки восходящей планарности графов, имеющих один источник, но несколько приемников, или наоборот. [12]
Проверка восходящей планарности может выполняться за полиномиальное время, когда имеется постоянное количество трехсвязных компонентов и разрезанных вершин, и выполняется с фиксированными параметрами в этих двух числах. [13] Его также можно использовать с фиксированными параметрами в цикломатическом числе входного графа. [14] Он также регулируется с фиксированным параметром по количеству источников (т.е. вершин без внутренних ребер) [15]
Если координаты y всех вершин фиксированы, то выбор координат x , который делает рисование вверх плоским, можно найти за полиномиальное время. [16]
Однако NP-полным является определение того, имеет ли плосконаправленный ациклический граф с несколькими источниками и приемниками планарный рисунок вверх. [17]
Прямолинейный чертеж и требования к площади
Теорема Фари утверждает, что каждый планарный граф имеет рисунок, на котором его ребра представлены отрезками прямых линий, и то же самое верно и для плоского рисунка, направленного вверх: каждый планарный граф, направленный вверх, имеет плоский рисунок, направленный вверх. [18]
Прямолинейное изображение транзитивно редуцированного st -планарного графа вверх может быть получено методом доминирования , при этом все вершины имеют целочисленные координаты в сетке n × n . [19] Однако для некоторых других восходящих плоских графиков может потребоваться экспоненциальная площадь во всех их прямолинейных плоских рисунках, направленных вверх. [18] Если выбор вложения фиксирован, даже ориентированные ряды параллельных графов и ориентированных деревьев могут потребовать экспоненциальной области. [20]
Диаграммы Хассе
Плоские рисунки, направленные вверх, особенно важны для диаграмм Хассе частично упорядоченных множеств , поскольку эти диаграммы обычно необходимо рисовать вверх. В терминах теории графов они соответствуют транзитивно редуцированным ориентированным ациклическим графам; такой граф может быть сформирован из отношения покрытия частичного порядка, а сам частичный порядок образует отношение достижимости в графе. Если частично упорядоченный набор имеет один минимальный элемент, один максимальный элемент и имеет плоский рисунок, направленный вверх, то он обязательно должен образовывать решетку — набор, в котором каждая пара элементов имеет уникальную наибольшую нижнюю границу и уникальную наименьшую верхнюю границу. . [21] Диаграмма Хассе решетки плоская тогда и только тогда, когда ее порядковая размерность не превосходит двух. [22] Однако некоторые частичные порядки размерности два и с одним минимальным и максимальным элементом не имеют плоского рисунка вверх (возьмем порядок, определяемый транзитивным замыканием ).
Рекомендации
Сноски
^ Гарг и Тамассия (1995); Ди Баттиста и др. (1998).
^ Гарг и Тамассия (1995), стр. 111–112; Ди Баттиста и др. (1998), 6.1 «Включение в планарный st -граф», стр. 172–179; Ди Баттиста и Тамассия (1988); Келли (1987).
^ Гарг и Тамассия (1995), стр. 112–115; Ди Баттиста и др. (1998), 6.2 «Углы в рисунках вверх», стр. 180–188; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994).
^ Гарг и Тамассия (1995), с. 115; Ди Баттиста и др. (1998), 6.7.2 «Запрещенные циклы для орграфов с одним источником», стр. 209–210; Томассен (1989).
^ Гарг и Тамассия (1995), с. 119; Ди Баттиста и др. (1998), с. 179.
^ Гарг и Тамассия (1995), стр. 119–121; Ди Баттиста и др. (1998), 6.3 «Тестирование восходящей планарности встроенных орграфов», стр. 188–192; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994); Аббаси, Хили и Рекстин (2010).
^ Ди Баттиста и др. (1998), стр. 191–192; Бертолацци и Ди Баттиста (1991); Бертолацци и др. (1994).
^ Гарг и Тамассия (1995), стр. 125–126; Ди Баттиста и др. (1998), 6.7.1 «Внепланарный орграф», с. 209; Папакостас (1995).
^ abc Ди Баттиста и др. (1998), 6.7.4 «Некоторые классы восходящих плоских орграфов», с. 212.
^ Дидимо, Джордано и Лиотта (2009).
^ Ди Баттиста, Лю и соперник (1990).
^ Гарг и Тамассия (1995), стр. 122–125; Ди Баттиста и др. (1998), 6.5 «Оптимальное тестирование восходящей планарности орграфов с одним источником», стр. 195–200; Хаттон и Любив (1996); Бертолацци и др. (1998).
^ Чан (2004); Хили и Линч (2006).
^ Хили и Линч (2006).
^ Чаплик и др. (2022)
^ Юнгер и Лейперт (1999).
^ Гарг и Тамассия (1995), стр. 126–132; Ди Баттиста и др. (1998), 6.6 «Тестирование восходящей планарности является NP-полным», стр. 201–209; Гарг и Тамассия (2001).
^ Аб Ди Баттиста и Фрати (2012); Ди Баттиста, Тамассия и Толлис (1992).
^ Ди Баттиста и др. (1998), 4.7 «Рисунки доминирования», стр. 112–127; Ди Баттиста, Тамассия и Толлис (1992).
^ Ди Баттиста и Фрати (2012); Бертолацци и др. (1994); Фрати (2008).
^ Ди Баттиста и др. (1998), 6.7.3 «Запрещенные конструкции для решеток», стр. 210–212; Платт (1976).
^ Гарг и Тамассия (1995), стр. 118; Бейкер, Фишберн и Робертс (1972).
Ди Баттиста, Джузеппе; Фрати, Фабрицио (2012), «Рисование деревьев, внешнепланарных графов, последовательно-параллельных графов и плоских графов на небольшой площади», Тридцать очерков по геометрической теории графов , алгоритмам и комбинаторике, том. 29, Спрингер, стр. 121–165, номер документа : 10.1007/978-1-4614-0110-0_9, ISBN.9781461401100. Раздел 5, «Рисунки вверх», стр. 149–151.
Бертолацци, Паола; Коэн, Роберт Ф.; Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1994), «Как нарисовать последовательно-параллельный орграф», Международный журнал вычислительной геометрии и приложений , 4 (4): 385–402, doi : 10.1142/S0218195994000215, MR 1310911.
Бертолацци, Паола; Ди Баттиста, Джузеппе (1991), «О тестировании рисования вверх трехсвязных орграфов», Труды седьмого ежегодного симпозиума по вычислительной геометрии (SCG '91, Норт-Конвей, Нью-Гэмпшир, США), Нью-Йорк, Нью-Йорк, США: ACM, стр. 272–280, номер документа : 10.1145/109648.109679, ISBN.0-89791-426-0, S2CID 18306721.
Бертолацци, П.; Ди Баттиста, Г.; Лиотта, Г.; Маннино, К. (1994), «Восходящие рисунки трехсвязных орграфов», Algorithmica , 12 (6): 476–497, doi : 10.1007/BF01188716, MR 1297810, S2CID 33167313.
Бертолацци, Паола; Ди Баттиста, Джузеппе; Маннино, Карло; Тамассиа, Роберто (1998), «Оптимальное тестирование восходящей планарности орграфов с одним источником», SIAM Journal on Computing , 27 (1): 132–169, doi : 10.1137/S0097539794279626, MR 1614821.
Ди Баттиста, Джузеппе; Лю, Вэй-Пин; Ривал, Иван (1990), «Двудольные графы, рисунки вверх и планарность», Information Processing Letters , 36 (6): 317–322, doi : 10.1016/0020-0190(90)90045-Y, MR 1084490.
Ди Баттиста, Джузеппе; Тамассиа, Роберто (1988), «Алгоритмы для плоских представлений ациклических орграфов», Theoretical Computer Science , 61 (2–3): 175–198, doi : 10.1016/0304-3975(88)90123-5 , MR 0980241.
Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1992), «Требования к площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (4): 381–401, doi : 10.1007/BF02187850 , MR 1148953.
Дидимо, Уолтер; Джордано, Франческо; Лиотта, Джузеппе (2009), «Тестирование восходящей спиральности и восходящей планарности», SIAM Journal on Discrete Mathematics , 23 (4): 1842–1899, doi : 10.1137/070696854, MR 2594962, S2CID 26154284.
Фрати, Фабрицио (2008), «О плоских направленных вверх рисунках направленных деревьев и других семейств направленных ациклических графов минимальной площади», Международный журнал вычислительной геометрии и приложений , 18 (3): 251–271, doi : 10.1142/S021819590800260X, MR 2424444.
Гарг, Ашим; Тамассиа, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Journal on Computing , 31 (2): 601–625, doi : 10.1137/S0097539794277123, MR 1861292, S2CID 15691098.
Хили, Патрик; Линч, Карол (2006), «Два управляемых алгоритма с фиксированными параметрами для проверки восходящей планарности», International Journal of Foundations of Computer Science , 17 (5): 1095–1114, doi : 10.1142/S0129054106004285.
Хаттон, Майкл Д.; Любив, Анна (1996), «Восходящий планарный рисунок ациклических орграфов с одним источником», SIAM Journal on Computing , 25 (2): 291–311, doi : 10.1137/S0097539792235906, MR 1379303. Впервые представлено на 2-м симпозиуме ACM-SIAM по дискретным алгоритмам, 1991 г.
