Русская Википедия:Угловое разрешение (теория графов)
Угловое разрешение рисунка графа относится к самому острому углу, образованному любыми двумя рёбрами, которые встречаются в одной вершине рисунка.
Свойства
Связь со степенью вершины
Форман с соавторамиШаблон:Sfn заметили, что любой рисунок графа с рёбрами-отрезками с максимальной степенью Шаблон:Mvar имеет угловое разрешение, не превосходящее <math>2\pi/d</math> — если Шаблон:Mvar является вершиной со степенью Шаблон:Mvar, то рёбра, инцидентные Шаблон:Mvar, разбивают пространство вокруг вершины Шаблон:Mvar на Шаблон:Mvar клиньев с суммарным углом <math>2\pi</math>, а наименьший из этих клиньев должен иметь угол, не превосходящий <math>2\pi/d</math>. Более строго, если граф является Шаблон:Mvar-регулярным, он должен иметь угловое разрешение, меньшее <math>\frac{\pi}{d-1}</math>, поскольку это лучшее разрешение, которое может быть получено для вершины на выпуклой оболочке рисунка.
Связь с раскраской графа
Как показали Форман с соавторамиШаблон:Sfn, наибольшее возможное угловое разрешение графа Шаблон:Mvar тесно связано с хроматическим числом квадрата графа Шаблон:Math, то есть графа с тем же набором вершин, в котором каждая пара вершин соединена ребром, если расстояние между ними в графе Шаблон:Mvar не превосходит двух. Если граф Шаблон:Math может быть раскрашен в <math>\chi</math> цветов, то G может быть нарисован с угловым разрешением <math>\pi/\chi - \epsilon</math> для любого <math>\epsilon > 0</math>, если назначить различные цвета вершинам правильного <math>\chi</math>-угольника и разместить каждую вершину графа Шаблон:Mvar рядом с вершиной многоугольника с тем же цветом. Используя это построение, они показали, что любой граф с максимальной степенью Шаблон:Mvar имеет рисунок с угловым разрешением, пропорциональным Шаблон:Math. Эта граница близка к точной — они использовали вероятностный метод для доказательства существования графов с максимальной степенью Шаблон:Mvar, все рисунки которых имеют угловое разрешение <math>O\left(\frac{\log d}{d^2}\right)</math>.
Существование оптимальных рисунков
Форман с соавторамиШаблон:Sfn привели пример, показывающий, что существуют графы, не имеющие рисунки с максимальным возможным угловым разрешением. Напротив, эти графы имеют семейство рисунков, угловые разрешения которых стремятся к некоторому ограниченному значения, но не достигают его. Конкретно, они представили граф с 11 вершинами, который имеет рисунок с угловым разрешением <math>\pi/3 - \epsilon</math> для любого <math>\epsilon > 0</math>, но не имеет рисунка с угловым разрешением, в точности равным <math>\pi/3</math>.
Специальные классы графов
Деревья
Любое дерево может быть нарисовано таким образом, что рёбра равномерно распределены вокруг каждой вершины, свойство, известное как совершенное угловое разрешение . Более того, если рёбра могут свободно переставляться вокруг каждой вершины, то такой рисунок возможен без пересечений с рёбрами длиной единица или более, а также весь рисунок помещается в прямоугольник полиномиальной площади. Однако, если циклическое упорядочение рёбер вокруг каждой вершины уже задано как часть условия задачи, то получение углового разрешения без пересечений может иногда потребовать экспоненциальной площадиШаблон:SfnШаблон:Sfn.
Внешнепланарные графы
Совершенное угловое разрешение не всегда возможно для внешнепланарных графов, поскольку вершины на выпуклой оболочки рисунка со степенью, большей единицы, не могут иметь инцидентные ей рёбра, равномерно распределённые вокруг вершины. Тем не менее, любой внешнепланарный граф с максимальной степенью Шаблон:Mvar имеет внешнепланарный рисунок с угловым разрешением, пропорциональным Шаблон:MathШаблон:SfnШаблон:Sfn.
Планарные графы
Для планарных графов с максимальной степенью Шаблон:Mvar техника раскрашивания квадрата графа Формана (с соавторами)Шаблон:Sfn даёт рисунок с угловым разрешением, пропорциональным Шаблон:Math, поскольку квадрат планарного графа должен иметь хроматическое число, пропорциональное Шаблон:Mvar. Вегнер высказал в 1977 году гипотезу, что хроматическое число квадрата планарного графа не превосходит <math>\max\left(d+5, \frac{3d}{2}+1\right)</math> и известно, что хроматическое число не превосходит <math>\frac{5d}{3}+O(1)</math>Шаблон:SfnШаблон:Sfn. Однако рисунок, получающийся по этой технике, в общем случае не планарен.
Для некоторых планарных графов оптимальное угловое разрешение планарного рисунка с рёбрами в виде отрезков равно Шаблон:Math, где Шаблон:Mvar является степенью графаШаблон:Sfn. Кроме того, такие рисунки могут вынужденно иметь очень длинные рёбра, более длинные, чем экспоненциальный множитель от самого короткого ребра рисунка. Малиц и ПапакостасШаблон:Sfn использовали теорему об упаковке кругов, чтобы показать, что любой планарный граф с максимальной степенью Шаблон:Mvar имеет планарный рисунок, угловое разрешение которого в худшем случае является экспоненциальной функцией от Шаблон:Mvar и не зависящей от числа вершин графа.
Вычислительная сложность
Задача определения, имеет ли данный граф с максимальной степенью Шаблон:Mvar рисунок с угловым разрешением <math>2\pi/d</math>, NP-трудна даже в специальном случае Шаблон:MathШаблон:SfnШаблон:Sfn. Однако для некоторых ограниченных классов рисунков, включая рисунки деревьев, в которых распространение листьев до бесконечности даёт выпуклое разбиение плоскости, как и рисунки планарных графов, в которых каждая ограниченная грань является центрально симметричным многоугольником, рисунок с оптимальным угловым разрешением может быть найден за полиномиальное времяШаблон:SfnШаблон:Sfn.
История
Угловое разрешение определили Форман с соавторамиШаблон:Sfn.
Хотя оно первоначально было определено для рисунков графов с прямолинейными рёбрами, позднее авторы исследовали угловое разрешение рисунков, в которых рёбра являются ломанымиШаблон:SfnШаблон:Sfn, дугами окружностейШаблон:SfnШаблон:Sfn или сплайнамиШаблон:SfnШаблон:Sfn.
Угловое разрешение графа тесно связано с его разрешением пересечений, углам, образованным пересечениями в рисунке графа. В частности, рисование графов под прямыми углами ищет представление, которое обеспечивает, чтобы все эти углы были прямыми, что является наибольшим возможным углом пересеченияШаблон:Sfn
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
