Одновременное внедрение

Одновременное встраивание — это метод в рисовании графов и визуализации информации для визуализации двух или более различных графов на одном и том же или перекрывающемся наборе помеченных вершин , избегая при этом пересечений внутри обоих графов. Пересечения между ребром одного графа и ребром другого графа разрешены. [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]

Ссылки

  1. ^ abcdefghijkl Блазиус, Томас; Кобуров, Стивен Г.; Раттер, Игнац (2013), «Одновременное вложение планарных графов», в Тамассиа, Роберто (ред.), Справочник по рисованию и визуализации графов , CRC Press, стр. 349–383, ISBN 9781420010268
  2. ^ ab Дункан, Кристиан; Эппштейн, Дэвид ; Кобуров, Стивен Г. (2004), «Геометрическая толщина графов низкой степени», Труды 20-го симпозиума ACM по вычислительной геометрии , ACM, стр. 340–346, arXiv : cs.CG/0312056 , doi :10.1145/997817.997868, S2CID  7595249.
  3. ^ Брасс, Питер; Ченек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф СБ (2007), «Об одновременных вложениях планарных графов», Computational Geometry Theory & Applications , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR  2278011.
  4. ^ Кабельо, Серджио; ван Кревелд, Марк; Лиотта, Джузеппе; Мейер, Хенк; Шпекманн, Беттина ; Вербек, Кевин (2011), «Геометрические одновременные вложения графа и сопоставления», Журнал графовых алгоритмов и приложений , 15 (1): 79–96, CiteSeerX 10.1.1.487.4749 , doi : 10.7155/jgaa.00218, МР  2776002 .
  5. ^ Эстрелла-Бальдеррама, Алехандро; Гасснер, Элизабет; Юнгер, Михаэль; Перкан, Мериам; Шефер, Маркус; Шульц, Михаэль (2008), «Одновременные геометрические вложения графов», Рисование графов : 15-й Международный симпозиум, GD 2007, Сидней, Австралия, 24–26 сентября 2007 г., Пересмотренные статьи , Заметки лекций по информатике, т. 4875, Берлин: Springer, стр. 280–290, doi : 10.1007/978-3-540-77537-9_28 , MR  2427826.
  6. ^ Кардинал, Жан; Кустерс, Винсент (2015), «Сложность одновременного геометрического вложения графов», Журнал графовых алгоритмов и приложений , 19 (1): 259–272, arXiv : 1302.7127 , doi : 10.7155/jgaa.00356 , MR  3344782, S2CID  12662906.
  7. ^ Блазиус, Кобуров и Раттер (2013), Рисунок 11.5.
  8. ^ ab Di Giacomo, Emilio; Liotta, Giuseppe (2007), «Одновременное вложение внешнепланарных графов, путей и циклов», International Journal of Computational Geometry & Applications , 17 (2): 139–160, doi :10.1142/S0218195907002276, MR  2309902.
  9. ^ Фрати, Фабрицио (2007), «Вложение графов одновременно с фиксированными ребрами», Рисование графов : 14-й Международный симпозиум, GD 2006, Карлсруэ, Германия, 18–20 сентября 2006 г., Пересмотренные статьи , Заметки лекций по информатике, т. 4372, Берлин: Springer, стр. 108–113, doi : 10.1007/978-3-540-70904-6_12 , MR  2393910.
  10. ^ Фаулер, Дж. Джозеф; Юнгер, Михаэль; Кобуров, Стивен Г.; Шульц, Михаэль (2011), «Характеристики ограниченных пар планарных графов, допускающих одновременное вложение с фиксированными ребрами», Computational Geometry Theory & Applications , 44 (8): 385–398, doi : 10.1016/j.comgeo.2011.02.002 , MR  2805957.
  11. ^ Гасснер, Элизабет; Юнгер, Михаэль; Перкан, Мериам; Шефер, Маркус; Шульц, Михаэль (2006), «Одновременные вложения графов с фиксированными ребрами», Графовые теоретические концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., пересмотренные статьи (PDF) , Lecture Notes in Computer Science, т. 4271, Берлин: Springer, стр. 325–335, doi :10.1007/11917496_29, MR  2290741.
  12. ^ Haeupler, Bernhard; Jampani, Krishnam Raju; Lubiw, Anna (2013), «Проверка одновременной планарности, когда общий граф является 2-связным», Journal of Graph Algorithms and Applications , 17 (3): 147–171, arXiv : 1009.4517 , doi : 10.7155/jgaa.00289, MR  3043207.
  13. ^ Ди Джакомо, Эмилио; Лиотта, Джузеппе (2005), «Заметка об одновременном вложении планарных графов», 21-й Европейский семинар по вычислительной геометрии (PDF) , Технический университет Эйндховена.
Взято с "https://en.wikipedia.org/w/index.php?title=Одновременное_встраивание&oldid=1235984293"