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

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

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

Примеры

Полный граф K5 имеет РПУ рисунок с прямыми рёбрами, а вот K6, нет. Любой РПУ рисунок с 6 вершинами имеет максимум 14 рёбер, а K6 имеет 15 рёбер, слишком много для РПУ рисунка.

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

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

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

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

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

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

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