На графике рисунка , А РСК рисунок из графика представляет собой чертеж , в котором вершины представлены в виде точек, края представлены в виде прямых отрезков прямых или ломаных линий , не более двух ребер пересекаются в любой точке, и когда пересекают два ребра они делают так под прямым углом друг к другу. В названии этого стиля рисования «RAC» означает «пересечение под прямым углом».
Стиль пересечения под прямым углом , и название «RAC рисунок» для этого стиля оба были сформулированы Didimo, Eades & Лиотт (2009) , [1] мотивированы предыдущими исследованиями пользователей , показывающих , что переходы с большими углами гораздо менее вредны для удобства чтения рисунков, чем неглубокие переходы. [2] Даже для плоских графиков , разрешение некоторых пересечений под прямым углом на чертеже графика может значительно улучшить показатели качества изображения, такие как его площадь или угловое разрешение . [3]
Примеры
Полный граф K 5 имеет RAC рисунок с прямыми краями, а К 6 не делает. Каждый 6-вершинный чертеж RAC имеет не более 14 ребер, но K 6 имеет 15 ребер, слишком много, чтобы иметь чертеж RAC. [1]
Полный двудольный граф К , б имеет RAC рисунок с прямыми краями тогда и только тогда , когда либо мин ( , б ) ≤ 2 или + б ≤ 7. Если мин ( , б ) ≤ 2, то граф является плоский граф , и (по теореме Фари ) каждый плоский граф имеет прямолинейный рисунок без пересечений. Такой чертеж автоматически является чертежом RAC. Остались только два случая - это графы K 3,3 и K 3,4 . Показан чертеж K 3,4 ; Из него можно образовать K 3,3 , удалив одну вершину. Ни на одном из следующих двух больших графиков, K 4,4 и K 3,5 , нет чертежа RAC. [4]
Кромки и изгибы
Если граф с n- вершинами имеет чертеж 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-трудно определить , имеет ли данный граф рац рисунок с прямыми краями, [10] , даже если входной граф является 1-планарным и выход РСК рисунок должен быть 1-планарным , а также. [11] Проблема рисования RAC остается NP-сложной для рисования вверх ориентированных ациклических графов . [12] Однако в частном случае внешне-1-планарных графов чертеж RAC может быть построен за линейное время. [13]
Рекомендации
- ^ a b c d Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графов с пересечениями под прямым углом», Алгоритмы и структуры данных : 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г. Труды , Лекционные заметки по компьютерным наукам , 5664 , стр. . 206–217, DOI : 10.1007 / 978-3-642-03367-4_19.
- ^ Хуанг, Вэйдун; Хонг, Сок-Хи; Идс, Питер (2008), «Эффекты пересечения углов», IEEE Pacific Visualization Symposium (PacificVIS '08) , стр. 41–46, doi : 10.1109 / PACIFICVIS.2008.4475457.
- ^ Ван Кревельд, Марк (2011), «Соотношение качества чертежей RAC и плоских чертежей планарных графиков», Рисование графиков : 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , конспекты лекций в области компьютерных наук, 6502 ., С. 371-376, DOI : 10.1007 / 978-3-642-18469-7_34.
- ^ Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2010), "Характеристика полных графов двудольный RAC", Information Processing Letters , 110 (16): 687-691, DOI : 10.1016 / j.ipl.2010.05.023 , MR 2676805.
- ^ Анджелини, Патрицио; Бекос, Майкл; Ферстер, Генри; Кауфманн, Майкл (2018), О чертежах RAC графов с одним изгибом на ребро , arXiv : 1808.10470
- ^ Арикуши, Карин; Фулек, Радослав; Кесег, Балаж; Морич, Филип; Тот, Чаба Д. (2012), «Графы, допускающие рисунки с пересечением под прямым углом», Computational Geometry Theory & Applications , 45 (4): 169–177, arXiv : 1001.3117 , doi : 10.1016 / j.comgeo.2011.11.008 , Руководство по ремонту 2876688.
- ^ а б Идс, Питер ; Лиотта, Джузеппе (2013), "Правильные графы угла пересечения и 1-плоскостность", дискретная прикладная математика , 161 (7-8): 961-969, DOI : 10.1016 / j.dam.2012.11.019 , MR 3030582.
- ^ Аккерман, Эяль (2014), "Замечание по 1-планарных графов", дискретное Прикладная математика , 175 : 104-108, DOI : 10.1016 / j.dam.2014.05.025 , MR 3223912.
- ^ Дехкорди, Хуман Рейси; Eades, Питер (2012), "Каждый внешний 1-плоскость граф имеет прямой угол пересечения рисунок", Международный журнал вычислительной геометрии и приложений , 22 (6): 543-557, DOI : 10.1142 / S021819591250015X , MR 3042921.
- ^ Argyriou, Evmorfia N .; Бекос, Майкл А .; Симвонис, Антониос (2011 г.), «Задача рисования прямой RAC-системы является NP-сложной», SOFSEM 2011: 37-я конференция по текущим тенденциям в теории и практике компьютерных наук, Новый Смоковец, Словакия, 22-28 января 2011 г., Труды , Конспект лекций по информатике, 6543 , стр. 74–85, arXiv : 1009.5227 , Bibcode : 2011LNCS.6543 ... 74A , doi : 10.1007 / 978-3-642-18381-2_6
- ^ Бекос, Майкл А .; Дидимо, Уолтер; Лиотта, Джузеппе; Мехраби, Саид; Монтеккиани, Фабрицио (2017), «На чертежах RAC 1-плоских графов», Теоретическая информатика , 689 : 48–57, arXiv : 1608.08418 , doi : 10.1016 / j.tcs.2017.05.039
- ^ Анджелини, Патрицио; Читтадини, Лука; Ди Баттиста, Джузеппе; Дидимо, Уолтер; Фрати, Фабрицио; Кауфманн, Майкл; Симвонис, Антониос (2010 г.), «О перспективах, открываемых рисунками, пересекающими под прямым углом», Графическое изображение : 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Исправленные статьи , Лекционные заметки по информатике , 5849 , стр. 21–32, DOI : 10.1007 / 978-3-642-11805-0_5.
- ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж .; Ханауэр, Катрин; Глайсснер, Андреас; Нойвирт, Даниэль; Рейсльхубер, Йозеф (2013). «Распознавание внешних 1-планарных графов в линейном времени». Графическое рисование LNCS . 8284 : 107–118. DOI : 10.1007 / 978-3-319-03841-4 .