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

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

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