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

найменша можлива кількість різних кутових коефіцієнтів ребер у малюнку графа

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

Малюнок графа Петерсена з числом нахилів 3

Повні графи ред.

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

Зв'язок зі степенем графа ред.

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

Існують графи з найбільшим степенем 5, що мають довільно велике число нахилів[2]. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилів[3]. Результат Вейда і Чу (Помилка скрипту: Функції «harvard_core» не існує.) для повного графа   показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґратки[4]. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4[5].

 
Метод Кезега, Паха та Палвелді[6] комбінування пакування кіл і дерева квадрантів для отримання обмеженого числа нахилів для планарних графів з обмеженим степенем

Планарні графи ред.

Як показали Кезег, Пах і Палвелді (Помилка скрипту: Функції «harvard_core» не існує.), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса (Помилка скрипту: Функції «harvard_core» не існує.) для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують теорема про упаковку кіл для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженим[7], звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.

Складність ред.

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

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

Примітки ред.

  1. Wade, Chu, 1994.
  2. Довели незалежно Барат, Матоушек, Вуд (Помилка скрипту: Функції «harvard_core» не існує.) і Пах, Палвелді (Помилка скрипту: Функції «harvard_core» не існує.), коли розв'язували задачу, яку поставив Дуймович, Судерман і Шарір (Помилка скрипту: Функції «harvard_core» не існує.). Див. теореми 5.1 і 5.2 у Паха і Шаріра (Помилка скрипту: Функції «harvard_core» не існує.).
  3. Муккамала, Сегеді (Помилка скрипту: Функції «harvard_core» не існує.), які покращили раніший результат Кезега, Палвелді, Тота (Помилка скрипту: Функції «harvard_core» не існує.). Див. теорему 5.3 у Паха і Шаріра (Помилка скрипту: Функції «harvard_core» не існує.).
  4. Mukkamala, Pálvölgyi, 2012.
  5. Pach, Sharir, 2009.
  6. Keszegh, Pach, Pálvölgyi, 2011.
  7. Hansen, 1988.
  8. Formann, Hagerup, Haralambides, Kaufmann, 1993.
  9. Eades, Hong, Poon, 2010.
  10. Maňuch, Patterson, Poon, Thachuk, 2011.
  11. Garg, Tamassia, 2001.

Література ред.