Число нахилів графа

У візуалізації графів і геометричній теорії графів^[en] число нахилів графа — це найменша можлива кількість різних кутових коефіцієнтів ребер у малюнку графа, на якому вершини подано точками евклідової площини, а ребрами є відрізки, які не проходять через вершини, неінцидентні цим ребрам.

Хоча близькі задачі комбінаторної геометрії вивчали й раніше (Скотт у 1970 і Джемісон у 1984), задачу визначення числа нахилів графа поставили Вейд і Чу^[1], показавши, що число нахилів графа з ${\displaystyle n}$ вершинами повного графа ${\displaystyle K_{n}}$ дорівнює рівно ${\displaystyle n}$. Малюнок графа з таким числом нахилів можна отримати, розташувавши вершини графа в кутах правильного многокутника.

Зрозуміло, що число нахилів графа з найбільшим степенем ${\displaystyle d}$ не менше ${\displaystyle \lceil d/2\rceil }$, оскільки максимум два інцидентні ребра вершини степеня d можуть лежати на одній прямій (мати один нахил). Точніше, число нахилів не менше лінійної деревності графа, оскільки ребра одного нахилу мають утворювати лінійний ліс, а лінійна деревність, у свою чергу, не менша ніж ${\displaystyle \lceil d/2\rceil }$.

Існують графи з найбільшим степенем 5, що мають довільно велике число нахилів^[2]. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилів^[3]. Результат Вейда і Чу (Wade, Chu, (1994)) для повного графа ${\displaystyle K_{4}}$ показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґратки^[4]. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4^[5].

Як показали Кезег, Пах і Палвелді (Keszegh, Pach, Pálvölgyi, (2011)), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса (Malitz, Papakostas, (1994)) для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують теорема про упаковку кіл для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженим^[7], звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.

Визначення, чи дорівнює число нахилів 2, є NP-повною задачею^[8][9][10]. Звідси випливає, що NP-складною задачею є визначення числа нахилів довільного графа або апроксимація цього числа з гарантованою ефективністю, кращою за 3/2.

Перевірка, чи можна зобратити планарний граф планарним малюнком із числом нахилів 2, також є NP-повною задачею^[11].