Чертеж РАК

При рисовании графа RAC чертеж графа - — это рисунок, на котором вершины представлены в виде точек, ребра представлены в виде отрезков прямых линий или полилиний , не более двух ребер пересекаются в любой точке, и когда два ребра пересекаются, они пересекаются. под прямым углом друг к другу. В названии этого стиля рисования «RAC» означает «пересечение под прямым углом».

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

Примеры

Полный граф К ₅ имеет рисунок RAC с прямыми ребрами, а К ₆ — нет. Каждый чертеж RAC с 6 вершинами имеет не более 14 ребер, но K ₆ имеет 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 . чертеж К _3,4 Показан ; К _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 ]}

Ссылки

^ Jump up to: ^а ^б ^с ^д Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графиков с пересечениями под прямым углом», Алгоритмы и структуры данных : 11-й международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г. Труды , конспекты лекций по информатике , том. 5664, стр. 206–217, номер документа : 10.1007/978-3-642-03367-4_19 , ISBN. 978-3-642-03366-7 .
^ Хуан, Вэйдун; Хонг, Сок Хи ; Идс, Питер (2008), «Эффекты углов пересечения», Тихоокеанский симпозиум по визуализации IEEE (PacificVIS '08) , стр. 41–46, doi : 10.1109/PACIFICVIS.2008.4475457 , ISBN 978-1-4244-1966-1 .
^ ван Кревельд, Марк (2011), «Соотношение качества рисунков RAC и плоских рисунков плоских графов», Рисование графиков : 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , конспекты лекций в области компьютерных наук, вып. 6502, стр. 371–376, номер документа : 10.1007/978-3-642-18469-7_34 , ISBN. 978-3-642-18468-0 .
^ Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (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 .
^ Jump up to: ^а ^б Идс, Питер ; Лиотта, Джузеппе (2013), «Графы прямоугольных пересечений и 1-планарность», Discrete Applied Mathematics , 161 (7–8): 961–969, doi : 10.1016/j.dam.2012.11.019 , MR 3030582 .
^ Акерман, Эяль (2014), «Заметки об 1-плоских графах», Discrete Applied Mathematics , 175 : 104–108, doi : 10.1016/j.dam.2014.05.025 , MR 3223912 .
^ Дехкорди, Хуман Рейси; Идс, Питер (2012), «Каждый граф внешней 1-плоскости имеет рисунок пересечения под прямым углом», International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi : 10.1142/S021819591250015X , MR 3042921 .
^ Аргириу, Евморфия Н.; Бекос, Майкл А.; Симвонис, Антониос (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 , ISBN 978-3-642-18380-5
^ Бекос, Майкл А.; Дидимо, Уолтер; Лиотта, Джузеппе; Мехраби, Саид; Монтеккиани, Фабрицио (2017), «О RAC-чертежах 1-планарных графов», Theoretical Computer Science , 689 : 48–57, arXiv : 1608.08418 , doi : 10.1016/j.tcs.2017.05.039
^ Шефер, Маркус (2021), «RAC-вытяжка — это $\exists \mathbb {R}$ -complete», Труды 29-го Международного симпозиума по рисованию графов и сетевой визуализации (GD 2021) , arXiv : 2107.11663
^ Анджелини, Патрицио; Читтадини, Лука; Ди Баттиста, Джузеппе; Дидимо, Уолтер; Фрати, Фабрицио; Кауфманн, Майкл; Симвонис, Антониос (2010), «О перспективах, открываемых рисунками, пересекающими прямые углы», Рисунок графика : 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Переработанные статьи , Конспекты лекций по информатике , том. 5849, стр. 21–32, номер документа : 10.1007/978-3-642-11805-0_5 , ISBN. 978-3-642-11804-3 .
^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж.; Ханауэр, Катрин; Гляйснер, Андреас; Нойвирт, Дэниел; Рейслубер, Йозеф (2013), «Распознавание внешних 1-планарных графов в линейное время», Рисование графиков LNCS , Конспекты лекций по информатике, 8284 : 107–118, doi : 10.1007/978-3-319-03841-4 , ISBN 978-3-319-03840-7

[del09-1] Jump up to: ^а ^б ^с ^д Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графиков с пересечениями под прямым углом», Алгоритмы и структуры данных : 11-й международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г. Труды , конспекты лекций по информатике , том. 5664, стр. 206–217, номер документа : 10.1007/978-3-642-03367-4_19 , ISBN. 978-3-642-03366-7 .

[2] Хуан, Вэйдун; Хонг, Сок Хи ; Идс, Питер (2008), «Эффекты углов пересечения», Тихоокеанский симпозиум по визуализации IEEE (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, номер документа : 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

[6] Арикуши, Карин; Фулек, Радослав; Кесег, Балаж; Морич, Филип; Тот, Чаба Д. (2012), «Графики, допускающие рисунки пересечений под прямым углом», Computational Geometry Theory & Applications , 45 (4): 169–177, arXiv : 1001.3117 , doi : 10.1016/j.comgeo.2011.11.008 , МР 2876688 .

[el12-7] Jump up to: ^а ^б Идс, Питер ; Лиотта, Джузеппе (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 .

[de12-9] Дехкорди, Хуман Рейси; Идс, Питер (2012), «Каждый граф внешней 1-плоскости имеет рисунок пересечения под прямым углом», International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi : 10.1142/S021819591250015X , MR 3042921 .

[10] Аргириу, Евморфия Н.; Бекос, Майкл А.; Симвонис, Антониос (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 , ISBN 978-3-642-18380-5

[11] Бекос, Майкл А.; Дидимо, Уолтер; Лиотта, Джузеппе; Мехраби, Саид; Монтеккиани, Фабрицио (2017), «О RAC-чертежах 1-планарных графов», Theoretical Computer Science , 689 : 48–57, arXiv : 1608.08418 , doi : 10.1016/j.tcs.2017.05.039

[12] Шефер, Маркус (2021), «RAC-вытяжка — это $\exists \mathbb {R}$ -complete», Труды 29-го Международного симпозиума по рисованию графов и сетевой визуализации (GD 2021) , arXiv : 2107.11663

[13] Анджелини, Патрицио; Читтадини, Лука; Ди Баттиста, Джузеппе; Дидимо, Уолтер; Фрати, Фабрицио; Кауфманн, Майкл; Симвонис, Антониос (2010), «О перспективах, открываемых рисунками, пересекающими прямые углы», Рисунок графика : 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Переработанные статьи , Конспекты лекций по информатике , том. 5849, стр. 21–32, номер документа : 10.1007/978-3-642-11805-0_5 , ISBN. 978-3-642-11804-3 .

[14] Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж.; Ханауэр, Катрин; Гляйснер, Андреас; Нойвирт, Дэниел; Рейслубер, Йозеф (2013), «Распознавание внешних 1-планарных графов в линейное время», Рисование графиков LNCS , Конспекты лекций по информатике, 8284 : 107–118, doi : 10.1007/978-3-319-03841-4 , ISBN 978-3-319-03840-7

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]