Число наклонов графа

В визуализации графов и геометрической теории графов^[англ.] число наклонов графа — это минимальное возможное число различных коэффициентов наклона рёбер в рисунке графа, в котором вершины представляются точками евклидовой плоскости, а рёбрами являются отрезки, которые не проходят через вершины, неинцидентные этим рёбрам.

Хотя близкие проблемы комбинаторной геометрии изучались ранее (Скоттом в 1970 году и Джемисоном в 1984 году), задачу определения числа наклонов графа поставили Вейд и Чу ^[1], показав, что число наклонов графа с n вершинами полного графа K_n равно в точности n. Рисунок графа с таким числом наклонов можно получить, расположив вершины графа в углах правильного многоугольника.

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

Существуют графы с максимальной степенью пять, имеющие произвольно большое число наклонов^[2]. Однако любой граф с максимальной степенью три имеет не более четырёх наклонов^[3]. Результат Вейда и Чу (Wade, Chu (1994) harvtxt error: якоря не существует: CITEREFWade,_Chu1994 (помощь)) для полного графа K₄ показывает, что эта граница точная. Не любой набор из четырёх наклонов подходит для рисования всех графов степени 3 — набор наклонов подходит для рисования тогда и только тогда, когда они являются наклонами сторон и диагоналей параллелограмма. В частности, любой граф степени 3 может быть нарисован так, что его рёбра либо параллельны осям, либо параллельны основным диагоналям целочисленной решётки^[4]. Неизвестно, ограничено или нет число наклонов графов с максимальной степенью четыре ^[5].

Как показали Кезег, Пах и Палвёлди(Keszegh, Pach, Pálvölgyi (2011) harvtxt error: якоря не существует: CITEREFKeszegh,_Pach,_Pálvölgyi2011 (помощь)), любой планарный граф имеет плоский рисунок в виде прямых отрезков, в котором число различных наклонов является функцией от степени графа. Их доказательство следует построению Малица и Папакостаса (Malitz, Papakostas (1994) harvtxt error: якоря не существует: CITEREFMalitz,_Papakostas1994 (помощь)) для ограничения углового разрешения планарных графов как функции степени. Ограничение степени осуществляется дополнением графа до максимального планарного графа без увеличения его степени более чем на постоянный множитель, а затем применяется теорема об упаковке кругов для представления этого расширенного графа как набора касающихся друг друга окружностей. Если степень начального графа ограничена, отношение радиусов смежных окружностей в упаковке будет также ограничено ^[7], откуда, в свою очередь, следует, что применение дерева квадрантов для всех вершин графа в точке внутри окружности даёт наклоны, являющиеся отношениями малых целых чисел. Число различных наклонов, получаемое при этом построении, является экспонентой от степени графа.

Задача определения, равно ли число наклонов двум, является NP-полной задачей^[8][9][10]. Отсюда следует, что является NP-сложной задачей определение числа наклонов произвольного графа или аппроксимация этого числа с гарантированной эффективностью, лучшей чем 3/2.

Является ли планарный граф планарным рисунком с двумя наклонами — это также NP-полная задача ^[11].