Рисование графов под прямыми углами

Рисование под прямыми углами (РПУ=right angle crossing, RAC) графа — это рисование, при котором вершины представлены точками, а рёбра представлены отрезками или ломаными, не более двух рёбер пересекаются в одной точке, и если два ребра пересекаются, они должны пересекаться под прямыми углами.

РПУ представление полного графа K₅ и полного двудольного графа K_3,4

Стиль рисования под прямыми углами и название "RAC drawing" для этого стиля предложили Дидимо, Идес и Лиотта^[1], и этот стиль возник после обнаружения, что рисунок графа с пересечением под большими углами читаются лучше, чем рисунки с малыми углами^[2]. Даже для планарных графов пересечение некоторых рёбер под прямыми углами может существенно улучшить некоторые характеристики рисунка, такие как площадь или угловое разрешение^[3].

Примеры

Полный граф K₅ имеет РПУ рисунок с прямыми рёбрами, а вот K₆, нет. Любой РПУ рисунок с 6 вершинами имеет максимум 14 рёбер, а K₆ имеет 15 рёбер, слишком много для РПУ рисунка^[1].

Полный двудольный граф K_a,b имеет РПУ рисунок с рёбрами в виде отрезков тогда и только тога, когда min(a,b) ≤ 2 или a + b ≤ 7. Если min(a,b) ≤ 2, то граф является планарным, и (по теореме Фари) любой планарный граф имеет рисунок в виде отрезков без пересечений. Такие рисунки автоматически попадают в класс RAC. Остаются только два случая, графы K_3,3 и K_3,4. Изображение K_3,4 показано на рисунке. K_3,3 может быть получен из K_3,4 путём удаления одной вершины. Ни один из графов K_4,4 и K_3,5 не имеет РПУ рисунка^[4].

Рёбра и изломы

Если граф с n вершинами имеет РПУ представление с рёбрами в виде отрезков, он может иметь максимум 4n − 10 рёбер. Ограничение является тесным — существуют графы с РПУ-представлением, имеющие в точности 4n − 10 рёбер^[1]. Для рисунков с рёбрами в виде ломаных граница числа рёбер графа зависит от числа изломов, разрешённых на одно ребро. Графы, имеющие РПУ представления с одним или двумя изломами на ребро, имеют O(n) рёбер. Конкретнее, с одним изломом число рёбер не может превосходить 6.5n, а с двумя изломами — 74.2n^[5]. Любой граф имеет РПУ-представление, если разрешено три излома на ребро^[1].

Отношение к 1-планарности

Граф является 1-планарным, если он имеет рисунок с максимум одним пересечением на ребро. Интуитивно ясно, что это ограничение облегчает представление графа с пересечением рёбер под прямым углом, а ограничение 4n − 10 числа рёбер РПУ представления с рёбрами в виде отрезков близко границе 4n − 8 числа рёбер 1-планарных графов и близко границе 4n − 9 числа рёбер в представлении 1-планарных графов с рёбрами в виде отрезков. Любое РПУ представление с 4n − 10 рёбрами является 1-планарным^[6][7]. Кроме того, любой 1-внешнепланарный граф (это граф с одним пересечением на ребро, в котором все вершины лежат на внешней грани рисунка) имеет РПУ представление^[8]. Однако существуют 1-планарные графы с 4n − 10 рёбрами, не имеющие РПУ представления^[6].

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

Задача определения, имеет ли граф РПУ представление с рёбрами в виде отрезков, является NP-трудной^[9] и построение РПУ-рисунка аналогично возсходящему планарному рисованию^[10]. Однако в специальном случае 1-внешнепланарных графов, РПУ-представление может быть построено за линейное время^[11].