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

Рисунок графа Петерсона с числом наклонов 3

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

Полные графы

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

Связь со степенью графа

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

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

Метод Кезега, Паха и Палвёлди комбинирования упаковки кругов и дерева квадрантов для получения ограниченного числа наклонов для планарных графов с ограниченной степенью

Планарные графы

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

Сложность

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

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