Одновременное встраивание - Simultaneous embedding

Одновременное встраивание это техника в рисунок графика и визуализация информации для визуализации двух или более разных графики на одинаковых или перекрывающихся наборах помеченных вершины, избегая переходы в пределах обоих графиков. Переходы между край одного графа и ребро другого.[1]

Если края разрешено рисовать как полилинии или же кривые, то любой планарный граф может быть нарисован без пересечения его вершин в произвольных положениях на плоскости, где одно и то же размещение вершин обеспечивает одновременное вложение. [1]

Существуют две ограниченные модели: одновременное геометрическое вложение, где каждый граф должен быть нарисован планарно с отрезками линий, представляющими его края, а не более сложными кривыми, ограничивающими два заданных графа подклассами плоских графов, и одновременное вложение с фиксированными ребрами, где кривые или изгибы разрешены на ребрах, но любое ребро в обоих графах должно быть представлено одной и той же кривой на обоих чертежах.[1]В неограниченной модели любые два плоских графа могут иметь одновременное вложение.

Определение

Одновременный встраивание это техника в рисунок графика и визуализация информации для визуализации двух или более разных графики на одинаковых или перекрывающихся наборах помеченных вершины, избегая переходы в пределах обоих графиков. Переходы между край одного графа и ребро другого графа разрешены; запрещены только пересечения между двумя ребрами одного и того же графа.[1]

Если края разрешено рисовать как полилинии или же кривые, то любой планарный граф может быть нарисован без пересечений с вершинами в произвольных положениях на плоскости. Использование одного и того же размещения вершин для двух графов обеспечивает одновременное вложение двух графов. Исследования были сосредоточены на поиске чертежей с небольшим количеством изгибов или с несколькими пересечениями между ребрами двух графов.[1]

Есть две ограниченные модели: одновременное геометрическое вложение и одновременное встраивание с фиксированными краями, где на краях разрешены кривые или изгибы, но любое ребро, присутствующее в обоих графах, должно быть представлено одной и той же кривой на обоих чертежах. Когда существует одновременное геометрическое вложение, оно автоматически также является одновременным вложением с фиксированными краями.[1]

Для задач одновременного вложения более чем в два графа стандартно предполагать, что все пары входных графов имеют то же пересечение, что и друг друга; то есть множества ребер и вершин графов образуют подсолнечник. Это ограничение известно как пересечение подсолнечника.[1]

Одновременное встраивание тесно связано с толщина, минимальное количество плоских подграфов, которые могут покрывать все ребра данного графа, и геометрическая толщина, минимальное количество цветов ребер, необходимое для рисования прямой линии данного графа без пересечения между одноцветными ребрами. В частности, толщина данного графа равна двум, если ребра графа можно разделить на два подграфа, которые имеют одновременное вложение, и геометрическая толщина равна двум, если ребра можно разделить на два подграфа с одновременным геометрическим вложением.[2]

Геометрический

При одновременном геометрическом вложении каждый граф должен быть изображен как планарный граф с линейными сегментами, представляющими его ребра, а не более сложными кривыми, ограничивающими два заданных графа подклассами плоских графов. Многие результаты по одновременному геометрическому вложению основаны на идее, что Декартовы координаты из двух данных графики 'вершины могут быть получены из свойств двух графов. Одним из основных результатов этого типа является тот факт, что любые два графы путей на одном и том же множестве вершин всегда имеют одновременное вложение. Чтобы найти такое вложение, можно использовать положение вершины в первом пути как ее Икс-координата, а положение той же вершины на втором пути, что и ее у-координат. Таким образом, первый путь будет нарисован как Икс-монотонный ломаная линия, тип кривой, которая автоматически не пересекает самопересечение, и второй путь будет аналогичным образом нарисован как у-монотонная ломаная линия.[3]:Теорема 11.1.

Этот тип рисования помещает вершины в целочисленная решетка линейных по графику размеров. Аналогично определенные макеты также работают с большими, но все же линейными размерами сетки, когда оба графика гусеницы или когда оба графики цикла. Одновременное вложение в сетку линейных размеров также возможно для любого количества графов, которые все звезды. Другие пары типов графов, которые всегда допускают одновременное встраивание, но для которых может потребоваться сетка большего размера, включают колесо графа и граф цикла, дерево и соответствие, или пара графов, оба из которых имеют максимум степень два. Однако существуют пары плоских графов и сопоставления или дерева и пути, которые не имеют одновременного геометрического вложения.[3]:Рисунок 11.2[4][5]

Проверить, допускают ли два графа одновременное геометрическое вложение, является NP-жесткий.[1][6] Точнее полная для экзистенциальная теория реальности. Доказательство этого результата также подразумевает, что для некоторых пар графов, имеющих одновременные геометрические вложения, наименьшая сетка, на которой они могут быть построены, имеет двойной экспоненциальный размер.[7][2]Когда существует одновременное геометрическое вложение, оно автоматически также является одновременным вложением с фиксированными краями.[1]

Фиксированные края

При одновременном внедрении с фиксированными краями на краях допускаются кривые или изгибы, но любое ребро, присутствующее в обоих графах, должно быть представлено одной и той же кривой на обоих чертежах.[1] Классификация различных типов входных данных как всегда имеющих вложение или как иногда невозможных, зависит не только от двух типов графов, которые нужно нарисовать, но и от структуры их пересечения. Например, всегда можно найти такое вложение, когда оба из двух данных графов являются внешнепланарные графы и их пересечение есть линейный лес с не более чем одним сгибом на ребро, координатами вершин и точками сгиба, принадлежащими сетке полиномиальной площади. Однако существуют и другие пары внешнепланарных графов с более сложными пересечениями, которые не имеют такого вложения. Также возможно найти одновременное вложение с фиксированными ребрами для любой пары плоского графа и дерева.[3]:Рисунок 11.5.[8][9]

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Можно ли за полиномиальное время найти одновременное вложение с фиксированными ребрами для двух данных графов?
(больше нерешенных задач по математике)

Это открытый вопрос можно ли проверить существование одновременного вложения с фиксированными ребрами для двух данных графов в полиномиальное время. Однако для трех или более графиков проблема заключается в НП-полный. Когда существуют одновременные вложения с фиксированными ребрами, их можно найти за полиномиальное время для пар внешнепланарных графов и для Двусвязные графы, т.е. пары графов, пересечение которых двусвязно.[1][10][11][12]

Неограниченный

Любые два плоских графа могут быть вложены одновременно. Это может быть сделано в сетке полиномиальной площади с максимум двумя изгибами на край. Любые два субгамильтоновы графы иметь одновременное врезание с одним изгибом на каждую кромку.[1][8][13]

Рекомендации

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