Восходящее планарное представление

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

Направленный ациклический граф должен быть планарным, чтобы иметь восходящее планарное представление, но не всякий планарный ациклический граф имеет такое представление. Среди всех планарных направленных ациклических графов с единственным источником (вершиной, не имеющей входящих дуг) и стоком (вершиной, не имеющей исходящих дуг), графы с восходящими планарными представлениями — это st-планарные графы, планарные графы, в которых источник и сток принадлежат одной и той же грани по меньшей мере для одного планарного вложения графа. Более обще, граф G имеет восходящее планарное представление тогда и только тогда, когда он ориентированный, ациклический и является подграфом st-планарного графа на том же самом наборе вершин^[3][4][5][6].

В восходящем вложении множество входящих и исходящих дуг, инцидентных каждой вершине, следуют подряд в циклическом порядке дуг в вершине. Говорят, что планарное вложение заданного направленного ациклического графа бимодально, если оно обладает таким свойством. Кроме того, угол между двумя последовательными дугами с той же ориентацией в заданной вершине может быть помечен как малый, если он меньше ${\displaystyle \pi }$, или большой, если он больше ${\displaystyle \pi }$. Каждый сток должен иметь в точности один большой угол и любая вершина, не являющаяся ни источником, ни стоком, не должна иметь большого угла. Кроме того, каждая внутренняя грань представления должна иметь на два больше малых углов, чем больших, а внешняя грань должна иметь на два больше больших угла, чем малых углов. Правильное назначение — это разметка углов, которая удовлетворяет описанным свойствам. Любое восходящее вложение имеет правильное назначение. В обратную сторону, любой направленный ациклический граф, имеющий бимодальное планарное вложение с правильным назначением имеет восходящее планарное представление, которое может быть построено за линейное время^{[7][8][9][10]}.

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

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

• Проверку, является ли граф st-планарным, можно осуществить за линейное время путём добавления ребра из s в t и проверки, является ли оставшийся граф планарным. Вдоль тех же линий можно построить восходящее планарное представление (если существует) направленного ациклического графа с единственным источником и стоком за линейное время^[14][15].
• Проверку, можно ли ориентированный граф с фиксированным планарным вложением нарисовать как восходящий планарный с совместимым вложением, можно выполнить путём проверки, что вложение является бимодальным, и моделирования задачи совместимого назначения как задачи о потоке в сети. Время работы линейно от размера входного графа и полиномиально от числа источников и стоков^{[9][10][16][17][18]}.
• Поскольку направленные полиэдральные графы имеют единственное планарное вложение, существование восходящего планарного представления для этих графов может быть проверено за полиномиальное время^[9][10][19].
• Проверка, имеет ли внешнепланарный ориентированный ациклический граф восходящее планарное представление, также полиномиальна^[20][21][22].
• Любой параллельно-последовательный граф, ориентированный согласно параллельно-последовательной структуре, является восходяще планарным. Восходящее планарное представление может быть построено прямо из параллельно-последовательного разложения графа^[23]. Более обще, произвольная ориентация неориентированных параллельно-последовательных графов может быть проверена на восходящую планарность за полиномиальное время^[24].
• Любое ориентированное дерево^[англ.] восходяще планарно^[23].
• Любой двудольный планарный граф с рёбрами, ориентированными из одной доли в другую, восходяще планарен^[23][25].
• Известен более сложный алгоритм полиномиального времени для проверки восходящей планарности графов, имеющих единственный источник, но несколько стоков, или наоборот^{[26][27][28][29]}.
• Проверка восходящей планарности может быть осуществлена за полиномиальное время, если имеется постоянное число трисвязных компонент из числа вершинных сечений и эта проверка фиксированно-параметрически разрешима^[англ.] по этим двум числам^[30][31]. Проверка также фиксированно-параметрически разрешима по цикломатическому числу входного графа^[31].
• Если y-координаты всех вершин фиксированы, то x-координаты, которые делают представление восходяще планарным, можно найти за полиномиальное время^[32].

Однако задача определения, имеет ли восходящее планарное представление планарный направленный ациклический граф с несколькими источниками и несколькими стоками, является NP-полной^[33][34][35].

Теорема Фари утверждает, что любой планарный граф имеет представление, в котором рёбра представлены прямолинейными отрезками, и то же самое верно для восходящего планарного представления — любой восходящий планарный граф имеет восходящее планарное представление с дугами в виде прямолинейных отрезков^[36][37]. Прямолинейное восходящее представление транзитивно сокращённого st-планарного графа может быть получено с помощью техники доминирующего рисования^[англ.] со всеми вершинами, имеющими целых координат в решётке ${\displaystyle n\times n}$^[38][37]. Однако, некоторые другие восходящие планарные графы могут потребовать экспоненциальную площадь для всех их прямолинейных восходящих планарных представлений^[36][37]. Если способ вложения фиксирован, даже направленные параллельно-серийные графы и ориентированные деревья могут потребовать экспоненциальной площади^[36][39][40].

Восходящие планарные представления особо важны для диаграмм Хассе частично упорядоченных множеств, так как эти диаграммы обычно требуется рисовать в восходящем стиле. В терминах теории графов это соответствует транзитивно сокращенным направленным ациклическим графам. Такой граф можно сформировать из покрывающего отношения частичного порядка и частичный порядок сам по себе образует отношение достижимости в графе. Если частично упорядоченное множество имеет один минимальный элемент, имеет один максимальный элемент и имеет восходящее планарное представление, оно обязательно формирует решётку, множество, в котором любая пара элементов имеет единственную наибольшую нижнюю границу и единственную наименьшую верхнюю границу^[41][42]. Диаграмма Хассе решётки планарна тогда и только тогда, когда её порядковая размерность^[англ.] не превосходит двух^[43][44]. Однако некоторые частичные порядки размерности два с минимальными и максимальными элементами не имеют восходящего планарного представления (возьмём порядок, определённый транзитивным замыканием порядка ${\displaystyle a<b,a<c,b<d,b<e,c<d,c<e,d<f,e<f}$).