Меню

Главная
Случайная статья
Настройки
Рисование графов под прямыми углами
Материал из https://ru.wikipedia.org

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

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

Содержание

Примеры

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

Полный двудольный граф 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 не имеет РПУ рисунка[4].

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

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

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

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

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

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

Примечания
  1. 1 2 3 4 Didimo, Eades, Liotta, 2009, с. 206–217.
  2. Huang, Hong, Eades, 2008, с. 41–46.
  3. van Kreveld, 2011, с. 371–376.
  4. Didimo, Eades, Liotta, 2010, с. 687–691.
  5. Arikushi, Fulek, Keszegh и др., 2012, с. 169–177.
  6. 1 2 Eades, Liotta, 2013, с. 961–969.
  7. Ackerman, 2014, с. 104–108.
  8. Dehkordi, Eades, 2012, с. 543–557.
  9. Argyriou, Bekos, Symvonis, 2011, с. 74–85.
  10. Angelini, Cittadini, Di Battista и др., 2010, с. 21–32.
  11. Auer, Bachmaier, Brandenburg и др., 2013, с. 107-118.


Литература
Downgrade Counter