У візуалізації графів і число нахилів графа — це найменша можлива кількість різних кутових коефіцієнтів ребер у малюнку графа, на якому вершини подано точками евклідової площини, а ребрами є відрізки, які не проходять через вершини, неінцидентні цим ребрам.
Повні графи Хоча близькі задачі комбінаторної геометрії вивчали й раніше (Скотт у 1970 і Джемісон у 1984), задачу визначення числа нахилів графа поставили Вейд і Чу, показавши, що число нахилів графа з вершинами повного графа дорівнює рівно . Малюнок графа з таким числом нахилів можна отримати, розташувавши вершини графа в кутах правильного многокутника.
Зв'язок зі степенем графа Зрозуміло, що число нахилів графа з найбільшим степенем не менше , оскільки максимум два інцидентні ребра вершини степеня d можуть лежати на одній прямій (мати один нахил). Точніше, число нахилів не менше лінійної деревності графа, оскільки ребра одного нахилу мають утворювати лінійний ліс, а лінійна деревність, у свою чергу, не менша ніж .
Існують графи з найбільшим степенем 5, що мають довільно велике число нахилівДовели незалежно Барат, Матоушек, Вуд () і Пах, Палвелді (), коли розв'язували задачу, яку поставив Дуймович, Судерман і Шарір (). Див. теореми 5.1 і 5.2 у Паха і Шаріра ().. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилівМуккамала, Сегеді (), які покращили раніший результат Кезега, Палвелді, Тота (). Див. теорему 5.3 у Паха і Шаріра ().. Результат Вейда і Чу () для повного графа показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґратки. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4.
Планарні графи Як показали Кезег, Пах і Палвелді (), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса () для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують теорема про упаковку кіл для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженим, звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.
Складність Визначення, чи дорівнює число нахилів 2, є NP-повною задачею. Звідси випливає, що NP-складною задачею є визначення числа нахилів довільного графа або апроксимація цього числа з гарантованою ефективністю, кращою за 3/2.
Перевірка, чи можна зобратити планарний граф планарним малюнком із числом нахилів 2, також є NP-повною задачею.
Примітки
Література