Малювання графів із прямими кутами

Малюва́ння із прями́ми кута́ми (МПК=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, то граф є планарним, і (за теоремою Фарі) будь-який планарний граф має малюнок з відрізками без перетинів. Такі малюнки автоматично потрапляють до класу МПК. Залишаються тільки два випадки — графи 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] і побудова МПК-зображення аналогічна висхідному планарному поданню^[ru][10]. Однак у окремому випадку 1-зовніпланарних графів, МПК-подання можна побудувати за лінійний час^[11].