Кутова роздільність (теорія графів)

Малюнок цього графа гіперкуба має кутову роздільність $\pi /4$.

Кутова́ розді́льність малюнка графа стосується найгострішого кута, утвореного будь-якими двома ребрами, які зустрічаються в одній вершині малюнка.

Властивості

Зв'язок зі степенем вершини

Форман зі співавторамиШаблон:Sfn помітили, що будь-який малюнок графа з ребрами-відрізками з найбільшим степенем Шаблон:Mvar має кутову роздільність, що не перевищує $2\pi /d$ — якщо Шаблон:Mvar є вершиною зі степенем Шаблон:Mvar, то ребра, інцидентні Шаблон:Mvar, розбивають простір навколо вершини Шаблон:Mvar на Шаблон:Mvar клинів зі сумарним кутом $2\pi$, а найменший із цих клинів повинен мати кут, що не перевищує $2\pi /d$. Строгіше, якщо граф є Шаблон:Mvar-регулярним, він повинен мати кутову роздільність, меншу від $\frac{\pi }{d-1}$, оскільки це найкраща роздільність, яку можна отримати для вершини на опуклій оболонці малюнка.

Зв'язок із розфарбуванням графа

Як показали Форман зі співавторами Шаблон:Sfn, найбільша можлива кутова роздільність графа Шаблон:Mvar тісно пов'язана із хроматичним числом квадрата графа Шаблон:Math тобто графа з тим самим набором вершин, у якому кожна пара вершин з'єднана ребром, якщо відстань між ними у графі Шаблон:Mvar не перевищує двох. Якщо граф Шаблон:Math можна розфарбувати в $\chi$ кольорів, то G можна намалювати з кутовою роздільністю $\pi /\chi -ϵ$ для будь-кого $ϵ>0$, якщо призначити різні кольори вершинам правильного $\chi$-кутника і розмістити кожну вершину графа Шаблон:Mvar поруч із вершиною многокутника з тим самим кольором. Використовуючи цю побудову, вони показали, що будь-який граф з найбільшним степенем Шаблон:Mvar має малюнок із кутовою роздільністю, пропорційноюШаблон:Math. Ця межа близька до точної — вони використовували ймовірнісний метод для доведення існування графів з найбільшим степенем Шаблон:Mvar, всі малюнки яких мають кутову роздільність $O\left(\frac{\log d}{d^2}\right)$.

Існування оптимальних малюнків

Форман зі співавторамиШаблон:Sfn навели приклад, що показує, що існують графи, які не мають малюнків з найбільшою можливою кутовою роздільністю. Навпаки, ці графи мають сімейство малюнків, кутові роздільності яких прямують до деякого обмеженого значення, але не досягають його. Конкретно, вони представили граф із 11 вершинами, який має малюнок із кутовою роздільністю $\pi /3-ϵ$ для будь-кого $ϵ>0$, але не має малюнка з кутовою роздільністю, точно рівною $\pi /3$.

Окремі класи графів

Дерева

Будь-яке дерево можна намалювати так, щоб ребра виявились рівномірно розподіленими навколо кожної вершини, — властивість, відома як досконала кутова роздільність. Більше того, якщо ребра навколо кожної з вершин можна вільно переставляти, то такий малюнок можливий без перетинів з ребрами завдовжки одиниця або більше, а також весь малюнок міститься у прямокутнику поліноміальної площі. Однак, якщо циклічне впорядкування ребер навколо кожної вершини вже задано як частину умови задачі, отримання кутової роздільності без перетинів може іноді вимагати експоненціальної площіШаблон:SfnШаблон:Sfn.

Зовніпланарні графи

Досконала кутова роздільність не завжди можлива для зовніпланарних графів, оскільки вершина на опуклій оболонці малюнка зі степенем, більшим від одиниці, не може мати інцидентних їй ребер, рівномірно розподілених навколо вершини. Проте будь-який зовніпланарний граф з найбільшим степенем Шаблон:Mvar має зовніпланарний малюнок з кутовою роздільністю, пропорційноюШаблон:MathШаблон:SfnШаблон:Sfn.

Планарні графи

Для планарних графів із максимальним степенем Шаблон:Mvar техніка розфарбовування квадрата графа Формана (зі співавторами)Шаблон:Sfn дає малюнок з кутовою роздільністю, пропорційною Шаблон:Math, оскільки квадрат планарного графа повинен мати хроматичне число, пропорційне Шаблон:Mvar. Вегнер висловив 1977 року гіпотезу, що хроматичне число квадрата планарного графа не перевищує $\max (d+5,\frac{3d}{2}+1)$ і відомо, що хроматичне число не перевищує $\frac{5d}{3}+O(1)$Шаблон:SfnШаблон:Sfn. Однак малюнок, побудовнаий за цією технікою, в загальному випадку не планарний.

Для деяких планарних графів оптимальна кутова роздільність планарного малюнка з ребрами у вигляді відрізків дорівнює Шаблон:Math, де Шаблон:Mvar є степенем графаШаблон:Sfn. Крім того, такі малюнки можуть вимушено мати дуже довгі ребра, довші, ніж експоненційний множник від найкоротшого ребра малюнка. Маліц і ПапакостасШаблон:Sfn використали теорему про пакування кіл, щоб показати, що будь-який планарний граф з найбільшим степенем Шаблон:Mvar має планарний малюнок, кутова роздільність якого в гіршому випадку є експоненційною функцією від Шаблон:Mvar і яка залежить від числа вершин графа.

Обчислювальна складність

Задача визначення, чи має граф з найбільшим степенем Шаблон:Mvar малюнок з кутовою роздільністю $2\pi /d$, NP-складна навіть у частковому випадку Шаблон:MathШаблон:SfnШаблон:Sfn. Однак для деяких обмежених класів малюнків, зокрема для малюнків дерев, у яких поширення листя до нескінченності дає опукле розбиття площини, як і малюнки планарних графів, у яких кожна обмежена грань є центральносиметричним многокутником, рисунок з оптимальною кутовою роздільністю можна знайти за поліноміальний часШаблон:SfnШаблон:Sfn.

Історія

Кутову роздільність ввели Форман зі співавторамиШаблон:Sfn.

Хоча її спочатку визначено для малюнків графів із прямолінійними ребрами, пізніше автори досліджували кутову роздільність малюнків, на яких ребра є ламанимиШаблон:SfnШаблон:Sfn, дугами кілШаблон:SfnШаблон:Sfn або сплайнамиШаблон:SfnШаблон:Sfn.

Кутова роздільність графа тісно пов'язана з його роздільністю схрещень, тобто, кутами, утвореними схрещеннями на малюнку графа. Зокрема, під час малювання графів із прямими кутами шукають подання, яке забезпечує, щоб усі ці кути були прямими, що є найбільшим можливим кутом перетинуШаблон:Sfn.

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття