Чертеж РАК
Представление теории графов
Рисунки RAC полного графа K 5 и полного двудольного графа K 3,4

В графическом рисовании , рисунок RAC графа - это рисунок, в котором вершины представлены в виде точек, ребра представлены в виде отрезков прямых линий или полилиний , не более двух ребер пересекаются в любой точке, и когда два ребра пересекаются, они делают это под прямым углом друг к другу. В названии этого стиля рисования "RAC" означает "right angle crossing".

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

Примеры

Полный граф K 5 имеет рисунок RAC с прямыми ребрами, но K 6 — нет. Каждый рисунок RAC с 6 вершинами имеет не более 14 ребер, но K 6 имеет 15 ребер, слишком много, чтобы иметь рисунок RAC. [1]

Полный двудольный граф K a , b имеет рисунок RAC с прямыми ребрами тогда и только тогда, когда min( a , b ) ≤ 2 или a  +  b  ≤ 7. Если min( a , b ) ≤ 2, то граф является планарным графом , и (по теореме Фари ) каждый планарный граф имеет рисунок прямой линии без пересечений. Такой рисунок автоматически является рисунком RAC. Остаются только два случая: графы K 3,3 и K 3,4 . Показан рисунок K 3,4 ; K 3,3 может быть образован из него путем удаления одной вершины. Ни один из следующих двух больших графов, K 4,4 и K 3,5 , не имеет рисунка RAC. [4]

Края и изгибы

Если n -вершинный граф ( n ≥ 4) имеет рисунок RAC с прямыми ребрами, он может иметь не более 4 n  − 10 ребер. Это жестко: существуют графы, которые можно нарисовать с помощью RAC, с ровно 4 n  − 10 ребрами. [1] Для рисунков с ломаными ребрами ограничение на количество ребер в графе зависит от количества изгибов , которые разрешены для каждого ребра. Графы, которые имеют рисунки RAC с одним или двумя изгибами на ребро, имеют O( n ) ребер; более конкретно, с одним изгибом есть не более 5,5 n ребер [5] , а с двумя изгибами есть не более 74,2 n ребер. [6] Каждый граф имеет рисунок RAC с тремя изгибами на ребро. [1]

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

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

Сложность вычислений

NP -трудно определить, имеет ли заданный граф рисунок RAC с прямыми ребрами, [10] даже если входной граф является 1-планарным, а выходной рисунок RAC также должен быть 1-планарным. [11] Более конкретно, рисунок RAC является полным для экзистенциальной теории действительных чисел . [12] Задача рисунка RAC остается NP-трудной для рисования вверх направленных ациклических графов . [13] Однако в особом случае внешних 1-планарных графов рисунок RAC может быть построен за линейное время. [14]

Ссылки

  1. ^ abcd Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009), "Рисование графов с прямыми угловыми пересечениями", Алгоритмы и структуры данных : 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г. Труды , Lecture Notes in Computer Science , т. 5664, стр.  206–217 , doi :10.1007/978-3-642-03367-4_19, ISBN 978-3-642-03366-7.
  2. ^ Хуан, Вэйдонг; Хонг, Сок-Хи ; Идс, Питер (2008), «Эффекты углов пересечения», IEEE Pacific Visualization Symposium (PacificVIS '08) , стр.  41–46 , doi :10.1109/PACIFICVIS.2008.4475457, ISBN 978-1-4244-1966-1.
  3. ^ ван Кревельд, Марк (2011), «Соотношение качества рисунков RAC и планарных рисунков планарных графов», Рисование графов : 18-й международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспект лекций по информатике, т. 6502, стр.  371–376 , doi : 10.1007/978-3-642-18469-7_34 , ISBN 978-3-642-18468-0.
  4. ^ Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2010), «Характеристика полных двудольных графов RAC», Information Processing Letters , 110 (16): 687– 691, doi :10.1016/j.ipl.2010.05.023, MR  2676805.
  5. ^ Анджелини, Патрицио; Бекос, Михаэль; Фёрстер, Генри; Кауфманн, Михаэль (2018), «О RAC-рисунках графов с одним изгибом на ребро», arXiv : 1808.10470 [cs.DS]
  6. ^ Арикуши, Карин; Фулек, Радослав; Кесег, Балаж; Морич, Филип; Тот, Чаба Д. (2012), «Графики, допускающие рисунки пересечений под прямым углом», Computational Geometry Theory & Applications , 45 (4): 169–177 , arXiv : 1001.3117 , doi : 10.1016/j.comgeo.2011.11.008 , MR  2876688.
  7. ^ ab Eades, Peter ; Liotta, Giuseppe (2013), "Прямоугольные пересекающиеся графы и 1-планарность", Discrete Applied Mathematics , 161 ( 7– 8): 961– 969, doi : 10.1016/j.dam.2012.11.019 , MR  3030582.
  8. ^ Акерман, Эяль (2014), «Заметка об 1-планарных графах», Discrete Applied Mathematics , 175 : 104–108 , doi : 10.1016/j.dam.2014.05.025 , MR  3223912.
  9. ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), «Каждый внешний-1-плоскостной граф имеет рисунок пересечения под прямым углом», International Journal of Computational Geometry & Applications , 22 (6): 543–557 , doi :10.1142/S021819591250015X, MR  3042921.
  10. ^ Argyriou, Evmorfia N.; Bekos, Michael A.; Symvonis, Antonios (2011), "The straight-line RAC drawing problem is NP-hard", SOFSEM 2011: 37-я конференция по текущим тенденциям в теории и практике компьютерных наук, Новый Смоковец, Словакия, 22-28 января 2011 г., Труды , Lecture Notes in Computer Science, т. 6543, стр.  74–85 , arXiv : 1009.5227 , Bibcode : 2011LNCS.6543...74A, doi : 10.1007/978-3-642-18381-2_6, ISBN 978-3-642-18380-5
  11. ^ Бекос, Майкл А.; Дидимо, Уолтер; Лиотта, Джузеппе; Мехраби, Саид; Монтеккиани, Фабрицио (2017), «О рисунках RAC 1-планарных графов», Теоретическая информатика , 689 : 48–57 , arXiv : 1608.08418 , doi : 10.1016/j.tcs.2017.05.039
  12. ^ Шефер, Маркус (2021), «RAC-drawability is -complete», Труды 29-го Международного симпозиума по рисованию графов и визуализации сетей (GD 2021) , arXiv : 2107.11663 ∃ Р {\displaystyle \exists \mathbb {R} }
  13. ^ Анджелини, Патрицио; Читтадини, Лука; Ди Баттиста, Джузеппе; Дидимо, Вальтер; Фрати, Фабрицио; Кауфманн, Майкл; Симвонис, Антониос (2010), «О перспективах, открываемых прямыми угловыми пересекающимися рисунками», Graph Drawing : 17th International Symposium, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Revised Papers , Lecture Notes in Computer Science, т. 5849, стр.  21–32 , doi : 10.1007/978-3-642-11805-0_5 , ISBN 978-3-642-11804-3.
  14. ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж.; Ханауэр, Катрин; Гляйснер, Андреас; Нойвирт, Дэниел; Рейслухубер, Йозеф (2013), «Распознавание внешних 1-планарных графов в линейном времени», Рисование графиков , Конспекты лекций по информатике, том. 8284, стр.  107–118 , номер документа : 10.1007/978-3-319-03841-4_10, ISBN. 978-3-319-03840-7
Взято с "https://en.wikipedia.org/w/index.php?title=RAC_drawing&oldid=1270768975"