Русская Википедия:Рисование графов под прямыми углами

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:RAC drawings.svg
РПУ представление полного графа K5 и полного двудольного графа K3,4

Рисование под прямыми углами (РПУ=right angle crossing, RAC) графа — это рисование, при котором вершины представлены точками, а рёбра представлены отрезками или ломаными, не более двух рёбер пересекаются в одной точке, и если два ребра пересекаются, они должны пересекаться под прямыми углами.

Стиль рисования под прямыми углами и название "RAC drawing" для этого стиля предложили Дидимо, Идес и ЛиоттаШаблон:Sfn, и этот стиль возник после обнаружения, что рисунок графа с пересечением под большими углами читаются лучше, чем рисунки с малыми угламиШаблон:Sfn. Даже для планарных графов пересечение некоторых рёбер под прямыми углами может существенно улучшить некоторые характеристики рисунка, такие как площадь или угловое разрешениеШаблон:Sfn.

Примеры

Полный граф K5 имеет РПУ рисунок с прямыми рёбрами, а вот K6, нет. Любой РПУ рисунок с 6 вершинами имеет максимум 14 рёбер, а K6 имеет 15 рёбер, слишком много для РПУ рисункаШаблон:Sfn.

Полный двудольный граф Ka,b имеет РПУ рисунок с рёбрами в виде отрезков тогда и только тога, когда min(a,b) ≤ 2 или a + b ≤ 7. Если min(a,b) ≤ 2, то граф является планарным, и (по теореме Фари) любой планарный граф имеет рисунок в виде отрезков без пересечений. Такие рисунки автоматически попадают в класс RAC. Остаются только два случая, графы K3,3 и K3,4. Изображение K3,4 показано на рисунке. K3,3 может быть получен из K3,4 путём удаления одной вершины. Ни один из графов K4,4 и K3,5 не имеет РПУ рисункаШаблон:Sfn.

Рёбра и изломы

Если граф с n вершинами имеет РПУ представление с рёбрами в виде отрезков, он может иметь максимум 4n − 10 рёбер. Ограничение является тесным — существуют графы с РПУ-представлением, имеющие в точности 4n − 10 рёберШаблон:Sfn. Для рисунков с рёбрами в виде ломаных граница числа рёбер графа зависит от числа изломов, разрешённых на одно ребро. Графы, имеющие РПУ представления с одним или двумя изломами на ребро, имеют O(n) рёбер. Конкретнее, с одним изломом число рёбер не может превосходить 6.5n, а с двумя изломами — 74.2nШаблон:Sfn. Любой граф имеет РПУ-представление, если разрешено три излома на реброШаблон:Sfn.

Отношение к 1-планарности

Граф является 1-планарным, если он имеет рисунок с максимум одним пересечением на ребро. Интуитивно ясно, что это ограничение облегчает представление графа с пересечением рёбер под прямым углом, а ограничение 4n − 10 числа рёбер РПУ представления с рёбрами в виде отрезков близко границе 4n − 8 числа рёбер 1-планарных графов и близко границе 4n − 9 числа рёбер в представлении 1-планарных графов с рёбрами в виде отрезков. Любое РПУ представление с 4n − 10 рёбрами является 1-планарнымШаблон:SfnШаблон:Sfn. Кроме того, любой 1-внешнепланарный граф (это граф с одним пересечением на ребро, в котором все вершины лежат на внешней грани рисунка) имеет РПУ представлениеШаблон:Sfn. Однако существуют 1-планарные графы с 4n − 10 рёбрами, не имеющие РПУ представленияШаблон:Sfn.

Вычислительная сложность

Задача определения, имеет ли граф РПУ представление с рёбрами в виде отрезков, является NP-труднойШаблон:Sfn и построение РПУ-рисунка аналогично возсходящему планарному рисованиюШаблон:Sfn. Однако в специальном случае 1-внешнепланарных графов, РПУ-представление может быть построено за линейное времяШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Рисование_графов_под_прямыми_углами&oldid=10701293