На графике рисунка , вверх плоская рисунок из ориентированного ациклического графа является вложение графа в евклидовой плоскости , в которой ребра представлены в виде , не пересекая монотонные вверх кривые. То есть кривая, представляющая каждое ребро, должна иметь свойство, согласно которому каждая горизонтальная линия пересекает ее не более чем в одной точке, и никакие два ребра не могут пересекаться, кроме как в общей конечной точке. [1] В этом смысле это идеальный случай для рисования многоуровневого графа , стиля рисования графа, в котором ребра представляют собой монотонные кривые, которые могут пересекаться, но в котором пересечения должны быть минимизированы.
Характеристики
Направленный ациклический граф должен быть плоским , чтобы иметь восходящий плоский рисунок, но не каждый плоский ациклический граф имеет такой рисунок. Среди плоских ориентированных ациклических графов с одним источником (вершина без входящих ребер) и стоком (вершина без исходящих ребер), графы с направленными вверх плоскими графами являются st -планарными графами , плоскими графами, в которых оба источника и сток принадлежат. к той же грани хотя бы одного плоского вложения графа. В более общем смысле, граф G имеет направленный вверх плоский рисунок тогда и только тогда, когда он направлен и ацикличен, и является подграфом st -планарного графа на том же множестве вершин. [2]
В восходящем вложении наборы входящих и исходящих ребер, инцидентных каждой вершине, являются смежными в циклическом порядке ребер в вершине. Плоское вложение данного ориентированного ациклического графа называется бимодальным, если оно обладает этим свойством. Кроме того, угол между двумя соседними ребрами с одинаковой ориентацией в данной вершине может быть обозначен как малый, если он меньше π, или как большой, если он больше π. Каждый источник или сток должен иметь ровно один большой угол, и каждая вершина, которая не является ни источником, ни стоком, не должна иметь ни одного. Кроме того, каждая внутренняя грань чертежа должна иметь на два меньших угла больше, чем большие, а внешняя грань должна иметь на два больших угла больше, чем маленькие. Последовательное назначение является маркировка углов , который удовлетворяет эти свойства; каждое вложение вверх имеет последовательное назначение. И наоборот, каждый ориентированный ациклический граф, который имеет бимодальное плоское вложение с согласованным назначением, имеет восходящий планарный рисунок, который может быть построен из него за линейное время. [3]
Другая характеристика возможна для графиков с одним источником. В этом случае восходящее плоское вложение должно иметь источник на внешней грани, и каждый неориентированный цикл графа должен иметь хотя бы одну вершину, в которую входят оба ребра цикла (например, вершина с самым высоким расположением на чертеже) . И наоборот, если вложение обладает обоими этими свойствами, оно эквивалентно вложению снизу вверх. [4]
Вычислительная сложность
Известно, что за полиномиальное время возможно несколько частных случаев тестирования восходящей планарности :
- Проверить, является ли граф st -планарным, можно за линейное время , добавив ребро от s к t и проверив, является ли оставшийся граф плоским. Аналогичным образом можно построить восходящий плоский рисунок (если он существует) ориентированного ациклического графа с одним источником и стоком за линейное время. [5]
- Проверка того, может ли ориентированный граф с фиксированным планарным вложением быть нарисованным вверх плоским, с вложением, согласованным с данным, может быть выполнено путем проверки того, что вложение является бимодальным, и моделирования проблемы согласованного назначения как проблемы сетевого потока . Время работы линейно зависит от размера входного графа и полиномиально от количества его источников и стоков. [6]
- Поскольку ориентированные многогранные графы имеют уникальное плоское вложение, существование восходящего плоского рисунка для этих графов может быть проверено за полиномиальное время. [7]
- Тестирование ли внешнепланарный ориентированные ациклический граф имеет плоский вверх рисунок также многочлен. [8]
- Каждый последовательно-параллельный граф , ориентированный в соответствии с последовательно-параллельной структурой, является планарным снизу вверх. Планарный рисунок вверх может быть построен непосредственно из последовательно-параллельной декомпозиции графа. [9] В более общем смысле, произвольные ориентации неориентированных последовательно-параллельных графов могут быть проверены на планарность вверх за полиномиальное время. [10]
- Каждое ориентированное дерево плоско вверх. [9]
- Каждый двудольный плоский граф с его ребрами, последовательно ориентированными от одной стороны двудольного раздела к другой, является планарным снизу вверх [9] [11]
- Известен более сложный алгоритм с полиномиальным временем для проверки восходящей планарности графов, которые имеют один источник, но несколько приемников, или наоборот. [12]
- Тестирование восходящей планарности может быть выполнено за полиномиальное время, когда есть постоянное количество трехсвязных компонентов и вырезанных вершин, и с фиксированным параметром можно управлять этими двумя числами. [13] Это также фиксированный параметр, управляемый цикломатическим числом входного графа. [14]
- Если y -координаты всех вершин фиксированы, то выбор x -координат, который делает рисунок вверх плоским, может быть найден за полиномиальное время. [15]
Тем не менее, это NP-полный, чтобы определить, имеет ли планарно направленный ациклический граф с несколькими источниками и стоками направленный вверх плоский рисунок. [16]
Прямолинейный рисунок и требования к площади
Теорема Фари гласит, что у каждого плоского графа есть рисунок, на котором его ребра представлены отрезками прямых линий, и то же самое верно для восходящего плоского рисунка: каждый восходящий планарный граф имеет прямой восходящий плоский рисунок. [17] Прямолинейный восходящий рисунок транзитивно редуцированного st -планарного графа может быть получен методом рисования с преобладанием , при этом все вершины имеют целочисленные координаты в сетке n × n . [18] Однако для некоторых других восходящих планарных графиков может потребоваться экспоненциальная площадь на всех их прямолинейных восходящих плоских чертежах. [17] Если выбор вложения фиксирован, даже ориентированные последовательные параллельные графы и ориентированные деревья могут потребовать экспоненциальной площади. [19]
Диаграммы Хассе
Восходящее плоские чертежи особенно важны для Хассы диаграмм из частично упорядоченных множеств , так как эти схемы , как правило , должны быть сделаны вверх. В терминах теории графов они соответствуют транзитивно редуцированным ориентированным ациклическим графам; такой граф может быть сформирован из отношения покрытия частичного порядка, а сам частичный порядок формирует отношение достижимости в графе. Если частично упорядоченный набор имеет один минимальный элемент, один максимальный элемент и имеет направленный вверх плоский рисунок, то он обязательно должен образовывать решетку , набор, в котором каждая пара элементов имеет уникальную точную нижнюю границу и уникальную наименьшую верхнюю границу. . [20] Диаграмма Хассе решетки плоская тогда и только тогда, когда ее порядковая размерность не превосходит двух. [21] Однако некоторые частичные порядки размерности два и с одним минимальным и максимальным элементом не имеют направленного вверх плоского рисунка (возьмите порядок, определенный транзитивным замыканием).
Рекомендации
- Сноски
- ^ Гарг и Тамассия (1995) ; Di Battista et al. (1998) .
- ^ Garg & Tamassia (1995) , стр 111-112. Di Battista et al. (1998) , 6.1 «Включение в плоскостной й -граф», стр 172-179. Ди Баттиста и Тамассия (1988) ; Келли (1987) .
- ^ Garg & Tamassia (1995) , стр 112-115. Di Battista et al. (1998) , 6.2 «Углы на рисунках вверх», стр. 180–188; Бертолацци и Ди Баттиста (1991) ; Бертолацци и др. (1994) .
- ^ Garg & Tamassia (1995) , стр. 115; Di Battista et al. (1998) , 6.7.2 «Запрещенные циклы для одноисточников орграфов», стр. 209–210; Томассен (1989) .
- ^ Garg & Tamassia (1995) , стр. 119; Di Battista et al. (1998) , стр. 179.
- ^ Garg & Tamassia (1995) , стр 119-121. Di Battista et al. (1998) , 6.3 «Тестирование встроенных орграфов вверх на планарность», стр. 188–192; Бертолацци и Ди Баттиста (1991) ; Бертолацци и др. (1994) ; Аббаси, Хили и Рекстин (2010) .
- ^ Ди Баттиста и др. (1998) , стр. 191–192; Бертолацци и Ди Баттиста (1991) ; Бертолацци и др. (1994) .
- ^ Garg & Tamassia (1995) , стр 125-126. Di Battista et al. (1998) , 6.7.1 "Внешний планарный орграф", стр. 209; Папакостас (1995) .
- ^ а б в Ди Баттиста и др. (1998) , 6.7.4 "Некоторые классы восходящих плоских орграфов", стр. 212.
- ^ Дидимо, Джордано и Лиотта (2009) .
- ^ Ди Баттиста, Лю & Конкурент (1990) .
- ^ Garg & Tamassia (1995) , стр 122-125. Di Battista et al. (1998) , 6.5 «Тестирование оптимальной восходящей планарности орграфов из одного источника», стр. 195–200; Хаттон и Любив (1996) ; Бертолацци и др. (1998) .
- ^ Чан (2004) ; Хили и Линч (2006) .
- ^ Хили и Линч (2006) .
- ^ Юнгер и Leipert (1999) .
- ^ Garg & Tamassia (1995) , стр 126-132. Di Battista et al. (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) .
- ^ Garg & Tamassia (1995) , стр 118. Бейкер, Фишберн и Робертс (1972) .
- Обзоры и учебники
- Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Поток и восходящая планарность», Graph Drawing: Algorithms for the Visualization of Graph , Prentice Hall , pp. 171–213, ISBN 978-0-13-301615-4.
- Ди Баттиста, Джузеппе; Фрати, Фабрицио (2012), «Рисование деревьев, внешнепланарных графов, последовательно-параллельных графов и плоских графов на небольшой площади», Тридцать эссе по геометрической теории графов , алгоритмам и комбинаторике, 29 , Springer, стр. 121–165, doi : 10.1007 / 978-1-4614-0110-0_9 , ISBN 9781461401100. Раздел 5, «Рисунки снизу вверх», стр. 149–151.
- Гарг, Ашим; Tamassia, Роберто (1995), "Восходящее испытание плоскостности", заказ , 12 (2): 109-133, DOI : 10.1007 / BF01108622 , MR 1354797.
- Исследовательские статьи
- Аббаси, Сармад; Хили, Патрик; Rextin, Аймал (2010), "Улучшение время работы встроенного вверх тестирования планарности", Information Processing Letters , 110 (7): 274-278, DOI : 10.1016 / j.ipl.2010.02.004 , MR 2642837.
- Бейкер, К.А.; Фишберн, ПК; Робертс, Ф.С. (1972), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
- Бертолацци, Паола; Коэн, Роберт Ф .; Ди Баттиста, Джузеппе; Тамассия, Роберто ; Tollis, Иоаннис Г. (1994), "Как нарисовать последовательно-параллельный орграф", Международный журнал вычислительной геометрии и приложений , 4 (4): 385-402, DOI : 10,1142 / S0218195994000215 , MR 1310911.
- Бертолацци, Паола; Ди Баттиста, Джузеппе (1991), "О тестировании восходящего рисования трехсвязных диграфов", Труды седьмого ежегодного симпозиума по вычислительной геометрии (SCG '91, North Conway, New Hampshire, USA) , Нью-Йорк, Нью-Гэмпшир , США: ACM, . С. 272-280, DOI : 10,1145 / 109648,109679 , ISBN 0-89791-426-0.
- Bertolazzi, P .; Di Battista, G .; Liotta, G .; Маннино, С. (1994), "Upward чертежи трехсвязным орграфах", Algorithmica , 12 (6): 476-497, DOI : 10.1007 / BF01188716 , МР 1297810.
- Бертолацци, Паола; Ди Баттиста, Джузеппе; Маннино, Карло; Tamassia, Роберто (1998), "Оптимальное вверх тестирование плоскостность одного источника орграфах", SIAM журнал по вычислениям , 27 (1): 132-169, DOI : 10,1137 / S0097539794279626 , MR 1614821.
- Чан, Хуберт (2004), "Параметризованный алгоритм для проверки восходящей планарности", Proc. 12-й Европейский симпозиум по алгоритмам (ESA '04) , конспект лекций по информатике, 3221 , Springer-Verlag, стр. 157–168, doi : 10.1007 / 978-3-540-30140-0_16.
- Ди Баттиста, Джузеппе; Лю, Вэй-Пин; Конкурент, Иван (1990), "Двудольные графы, рисунки вверх, и плоскостность", Information Processing Letters , 36 (6): 317-322, DOI : 10.1016 / 0020-0190 (90) 90045-Y , МР 1084490.
- Ди Баттиста, Джузеппе; Tamassia, Роберто (1988), "Алгоритмы для плоских представлений ациклических орграфов", Теоретическая информатика , 61 (2-3): 175-198, DOI : 10,1016 / 0304-3975 (88) 90123-5 , MR 0980241.
- Ди Баттиста, Джузеппе; Тамассия, Роберто ; Tollis, Иоаннис Г. (1992), "Площадь требование и отображение симметрии плоских вверх чертежей", Дискретная и вычислительная геометрия , 7 (4): 381-401, DOI : 10.1007 / BF02187850 , МР 1148953.
- Дидимо, Уолтер; Джордано, Франческо; Лиотта, Джузеппе (2009), "вверх спиральности и вверх испытания плоскостности", SIAM журнал по дискретной математике , 23 (4): 1842-1899, DOI : 10,1137 / 070696854 , MR 2594962.
- Frati, Фабрицио (2008), «О минимальной площади плоской вверх чертежи направленных деревьев и других семейств ориентированных ациклических графов», Международный журнал вычислительной геометрии и приложений , 18 (3): 251-271, DOI : 10,1142 / S021819590800260X , М.Р. 2424444.
- Гарг, Ашим; Tamassia, Роберто (2001), "О вычислительной сложности вверх и прямолинейного тестирования планарности", SIAM журнал по вычислениям , 31 (2): 601-625, DOI : 10,1137 / S0097539794277123 , МР 1861292.
- Хили, Патрик; Линч, Кароль (2006), «Два управляемых алгоритма с фиксированными параметрами для тестирования восходящей планарности», Международный журнал основ компьютерных наук , 17 (5): 1095–1114, DOI : 10,1142 / S0129054106004285.
- Хаттон, Майкл Д .; Lubiw, Анна (1996), "вверх плоская чертеж одного источника ациклических орграфов", SIAM журнал по вычислениям , 25 (2): 291-311, DOI : 10,1137 / S0097539792235906 , МР 1379303. Впервые представлен на 2-м симпозиуме ACM-SIAM по дискретным алгоритмам в 1991 г.
- Юнгер, Михаэль; Лейперт, Себастьян (1999), «Плоское вложение в линейное время», Graph Drawing (Proc. GD '99) , Lecture Notes in Computer Science, 1731 , pp. 72–81, doi : 10.1007 / 3-540-46648- 7_7 , ISBN 978-3-540-66904-3.
- Келли, Дэвид (1987), "Основы плоских упорядоченных множеств", дискретной математики , 63 (2-3): 197-216, DOI : 10.1016 / 0012-365X (87) 90008-2 , МР - 0885497.
- Папакостас, Ахиллеас (1995), "Тестирование восходящей планарности внешнепланарных дагов (расширенная аннотация)", Рисование графика: Международный семинар DIMACS, GD '94, Принстон, Нью-Джерси, США, 10–12 октября 1994 г., Труды , Лекционные заметки в Computer Science, 894 , Берлин:. Springer, С. 298-306, DOI : 10.1007 / 3-540-58950-3_385 , MR 1337518.
- Платт, CR (1976), "Плоские решетки и плоские графы", Журнал комбинаторной теории , сер. В, 21 (1): 30–39, DOI : 10.1016 / 0095-8956 (76) 90024-1.
- Томасен, Карстен (1989), "плоскостной ациклические ориентированные графы", заказ , 5 (4): 349-361, DOI : 10.1007 / BF00353654 , МР 1010384.