Войти  |  Регистрация
Авторизация

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



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

Полные графы

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

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

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

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

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

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

Сложность

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

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


Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent