Одновременное встраивание
Одновременное встраивание — это метод рисования графов и визуализации информации, позволяющий визуализировать два или более разных графа на одном и том же или перекрывающемся наборе помеченных вершин , избегая при этом пересечений внутри обоих графов. Пересечения между ребром одного графа и ребром другого графа разрешены. [1]
Если разрешено рисовать ребра в виде полилиний или кривых , то любой плоский граф можно нарисовать без пересечения его вершин в произвольных положениях на плоскости, где одно и то же размещение вершин обеспечивает одновременное встраивание. [1]
Существуют две ограниченные модели: одновременное геометрическое встраивание, когда каждый граф должен быть нарисован плоско с отрезками линий, представляющими его ребра, а не более сложные кривые, ограничивая два заданных графа подклассами плоских графов, и одновременное встраивание с фиксированными ребрами, где кривые или на ребрах допускаются изгибы, но любое ребро на обоих графиках должно быть представлено одной и той же кривой на обоих рисунках. [1] В неограниченной модели любые два плоских графа могут иметь одновременное вложение.
Определение
[ редактировать ]Одновременное встраивание — это метод рисования графов и визуализации информации, позволяющий визуализировать два или более разных графа на одном и том же или перекрывающемся наборе помеченных вершин , избегая при этом пересечений внутри обоих графов. Пересечения между ребром одного графа и ребром другого графа разрешены; запрещены только пересечения двух ребер одного и того же графа. [1]
Если разрешено рисовать ребра в виде ломаных линий или кривых , то любой плоский граф можно нарисовать без пересечений с его вершинами в произвольных положениях на плоскости. Использование одного и того же размещения вершин для двух графов обеспечивает одновременное встраивание двух графов. Исследования были сосредоточены на поиске рисунков с небольшим количеством изгибов или с небольшим количеством пересечений между ребрами двух графов. [1]
Существуют две ограниченные модели: одновременное геометрическое встраивание и одновременное встраивание с фиксированными ребрами, где на ребрах допускаются кривые или изгибы, но любое ребро, присутствующее в обоих графах, должно быть представлено одной и той же кривой на обоих рисунках. Когда существует одновременное геометрическое вложение, оно автоматически также является одновременным вложением с фиксированными краями. [1]
Для задач одновременного внедрения более чем в два графа стандартно предполагается, что все пары входных графов имеют одинаковое пересечение друг с другом; то есть множества ребер и вершин графов образуют подсолнух . Это ограничение известно как пересечение подсолнечника . [1]
Одновременное встраивание тесно связано с толщиной — минимальным количеством плоских подграфов, которые могут покрыть все ребра данного графа, и геометрической толщиной — минимальным количеством цветов ребер, необходимых для прямолинейного рисунка данного графа без пересечений. между ребрами одного цвета. В частности, толщина данного графа равна двум, если ребра графа можно разбить на два подграфа, имеющих одновременное вложение, а геометрическая толщина равна двум, если ребра могут быть разбиты на два подграфа с одновременным геометрическим вложением. [2]
Геометрический
[ редактировать ]При одновременном геометрическом встраивании каждый граф должен быть нарисован как планарный граф с отрезками линий, представляющими его ребра, а не как более сложные кривые, ограничивая два данных графа подклассами плоских графов.Многие результаты по одновременному геометрическому встраиванию основаны на идее о том, что декартовы координаты вершин двух заданных графов могут быть получены из свойств двух графов. Одним из наиболее основных результатов этого типа является тот факт, что любые два графа путей на одном и том же множестве вершин всегда имеют одновременное вложение. Чтобы найти такое вложение, можно использовать положение вершины на первом пути в качестве ее координаты x , а положение той же вершины во втором пути в качестве ее y координаты . Таким образом, первый путь будет нарисован как монотонная по оси X ломаная линия , тип кривой, который автоматически не является самопересекающимся, а второй путь будет аналогичным образом нарисован как ломаная линия по оси y .
Этот тип рисования помещает вершины в целочисленную решетку с размерами, линейными по размерам графа. Аналогично определенные макеты также работают с более крупными, но все же линейными размерами сетки, когда оба графика являются гусеницами или когда оба являются циклическими графиками . Одновременное встраивание в сетку линейных размеров также возможно для любого количества графов, состоящих из звезд . Другие пары типов графов, которые всегда допускают одновременное встраивание, но для которых может потребоваться больший размер сетки, включают граф-колесо и граф-цикл, дерево и сопоставление или пару графов, оба из которых имеют максимальную степень два. Однако пары плоских графов и паросочетания Анджелини, Гейера, Нойвирта и Кауфмана показали, что существуют дерево и путь, которые не имеют одновременного геометрического вложения. [3] [4]
Проверка того, допускают ли два графа одновременное геометрическое вложение, NP-трудна . [1] [5] Точнее, она является полной для экзистенциальной теории реальностей . Доказательство этого результата также подразумевает, что для некоторых пар графов, имеющих одновременные геометрические вложения, наименьшая сетка, на которой они могут быть нарисованы, имеет вдвое экспоненциальный размер. [6] [2] Когда существует одновременное геометрическое вложение, оно автоматически также является одновременным вложением с фиксированными краями. [1]
Фиксированные края
[ редактировать ]При одновременном встраивании с фиксированными ребрами на ребрах допускаются кривые или изгибы, но любое ребро, присутствующее в обоих графах, должно быть представлено одной и той же кривой на обоих рисунках. [1] Классификация различных типов входных данных как всегда имеющих вложение или как иногда невозможных, зависит не только от двух типов рисуемых графов, но и от структуры их пересечения. Например, всегда можно найти такое вложение, когда оба из двух данных графов являются внешнепланарными графами , а их пересечение представляет собой линейный лес с не более чем одним изгибом на каждом ребре и с координатами вершин и точками изгиба, принадлежащими сетке из полиномиальная площадь. Однако существуют другие пары внешнепланарных графов с более сложными пересечениями, не имеющие такого вложения. Также возможно найти одновременное вложение с фиксированными ребрами для любой пары планарного графа и дерева. [7] [8] [9]
Остается открытым вопрос , можно ли проверить существование одновременного вложения с фиксированными ребрами для двух заданных графов за полиномиальное время . Однако для трех и более графов проблема является NP-полной . Когда одновременные вложения с фиксированными ребрами действительно существуют, их можно найти за полиномиальное время для пар внешнепланарных графов и для двусвязных графов , то есть пар графов, пересечение которых двусвязно. [1] [10] [11] [12]
Неограниченный
[ редактировать ]Любые два плоских графа могут иметь одновременное вложение. Это можно сделать в сетке полиномиальной площади, имеющей не более двух изгибов на ребро. Любые два субгамильтоновых графа имеют одновременное вложение не более чем с одним изгибом на каждое ребро. [1] [8] [13]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж г час я дж к л Блазиус, Томас; Кобуров, Стивен Г.; Раттер, Игнац (2013), «Одновременное встраивание плоских графов», в Тамассии, Роберто (редактор), Справочник по рисованию и визуализации графов , CRC Press, стр. 349–383, ISBN 9781420010268
- ^ Jump up to: а б Дункан, Кристиан; Эппштейн, Дэвид ; Кобуров, Стивен Г. (2004), «Геометрическая толщина графов низкой степени», Proc. ACM 20-й симпозиум по вычислительной геометрии , ACM, стр. 340–346, arXiv : cs.CG/0312056 , doi : 10.1145/997817.997868 , S2CID 7595249 .
- ^ Брасс, Питер; Сенек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф С.Б. (2007), «Об одновременных вложениях плоских графов», Теория и приложения вычислительной геометрии , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR 2278011 .
- ^ Кабельо, Серджио; ван Кревелд, Марк; Лиотта, Джузеппе; Мейер, Хенк; Шпекманн, Беттина ; Вербек, Кевин (2011), «Геометрические одновременные вложения графа и сопоставления», Журнал графовых алгоритмов и приложений , 15 (1): 79–96, CiteSeerX 10.1.1.487.4749 , doi : 10.7155/jgaa.00218 , МР 2776002 .
- ^ Эстрелла-Бальдеррама, Алехандро; Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (2008), «Одновременные вложения геометрических графов», Рисование графиков : 15-й Международный симпозиум, GD 2007, Сидней, Австралия, 24–26 сентября 2007 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 4875, Берлин: Springer, стр. 280–290, doi : 10.1007/978-3-540-77537-9_28 , MR 2427826 .
- ^ Кардинал, Жан; Кустерс, Винсент (2015), «Сложность одновременного внедрения геометрических графов», Журнал графовых алгоритмов и приложений , 19 (1): 259–272, arXiv : 1302.7127 , doi : 10.7155/jgaa.00356 , MR 3344782 , S2CID 12662906 .
- ^ Блазиус, Кобуров и Раттер (2013) , рисунок 11.5.
- ^ Jump up to: а б Ди Джакомо, Эмилио; Лиотта, Джузеппе (2007), «Одновременное встраивание внешнепланарных графов, путей и циклов», Международный журнал вычислительной геометрии и приложений , 17 (2): 139–160, doi : 10.1142/S0218195907002276 , MR 2309902 .
- ^ Фрати, Фабрицио (2007), «Вложение графов одновременно с фиксированными ребрами», Рисование графиков : 14-й Международный симпозиум, GD 2006, Карлсруэ, Германия, 18–20 сентября 2006 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 4372, Берлин: Springer, стр. 108–113, doi : 10.1007/978-3-540-70904-6_12 , MR 2393910 .
- ^ Фаулер, Дж. Джозеф; Юнгер, Майкл; Кобуров, Стивен Г.; Шульц, Майкл (2011), «Характеристики ограниченных пар плоских графов, позволяющие одновременное встраивание с фиксированными ребрами», Computational Geometry Theory & Applications , 44 (8): 385–398, doi : 10.1016/j.comgeo.2011.02.002 , МР 2805957 .
- ^ Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (2006), «Одновременные вложения графов с фиксированными краями», Теоретико-графовые концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., Переработанные статьи (PDF) , конспекты лекций в области компьютерных наук, вып. 4271, Берлин: Springer, стр. 325–335, номер документа : 10.1007/11917496_29 , MR 2290741 .
- ^ Хёплер, Бернхард; Джампани, Кришнам Раджу; Любив, Анна (2013), «Тестирование одновременной планарности, когда общий граф 2-связен», Журнал графовых алгоритмов и приложений , 17 (3): 147–171, arXiv : 1009.4517 , doi : 10.7155/jgaa.00289 , MR 3043207 .
- ^ Ди Джакомо, Эмилио; Лиотта, Джузеппе (2005), «Заметка об одновременном встраивании планарных графов», 21-й европейский семинар по вычислительной геометрии (PDF) , Технологический университет Эйндховена .