Википедия

Одновременное вложение графов

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

Определение править

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

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

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

Одновременное геометрическое вложение править

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

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

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

Одновременное вложение с фиксированными рёбрами править

Для одновременного вложения с фиксированными рёбрами классификация различных видов входных графов, всегда имеющих вложение или иногда не имеющих вложения, зависит не только от типов двух участвующих графов, но и также от структуры их пересечения. Например, когда оба графа являются внешнепланарными и их пересечение является линейным лесом, всегда можно найти такое вложение, которое имеет не более одного излома на ребро с вершинами и точками излома на решётке с размером, полиномиально зависящим от размера графа. Существуют, однако, другие пары внешнепланарных графов с более сложными пересечениями, не имеющими такого вложения. Можно также найти одновременное вложение с фиксированными рёбрами для любой пары планарного графа и дерева[9][10][11].

Нерешённые проблемы математики: Можно ли найти одновременное вложение с фиксированными рёбрами для двух заданных графов за полиномиальное время?

Является открытой проблемой, можно ли проверить существование одновременного вложения с фиксированными рёбрами за полиномиальное время. Однако для трёх и более графов задача NP-трудна. Одновременное вложение с фиксированными рёбрами можно найти (если таковое существует) за полиномиальное время для пары внешенпланарных графов, а также для пары графов, пересечение которых двусвязно[1][12][13][14].

Неограниченное одновременное вложение править

Любые два планарных графа имеют одновременное вложение. Это можно сделать на решётке полиномиального размера, рёбра при этом будут иметь не более двух изломов. Любые два подгамильтонова графа имеют одновременное вложение в максимум одним изломом на ребро[1][15].

Примечания править

  1. ↑ 1 2 3 4 5 6 7 Bläsius, Kobourov, Rutter, 2013, с. 349–383.
  2. ↑ Bläsius, Kobourov, Rutter, 2013, с. Theorem 11.1.
  3. ↑ Bläsius, Kobourov, Rutter, 2013, с. Figure 11.2.
  4. ↑ Brass, Cenek и др., 2007, с. 117–130.
  5. ↑ Cabello, van Kreveld и др., 2011, с. 79–96.
  6. ↑ Estrella-Balderrama, Gassner, Jünger, Percan, Schaefer, Schulz, 2008, с. 280–290.
  7. ↑ Cardinal, Kusters, 2015, с. 259–272.
  8. ↑ Duncan, Eppstein, Kobourov, 2004, с. 340–346.
  9. ↑ Bläsius, Kobourov, Rutter, 2013, с. Figure 11.5.
  10. ↑ Di Giacomo, Liotta, 2007, с. 139–160.
  11. ↑ Frati, 2007, с. 108–113.
  12. ↑ Fowler, Jünger, Kobourov, Schulz, 2011, с. 385–398.
  13. ↑ Gassner, Jünger, Percan, Schaefer, Schulz, 2006, с. 325–335.
  14. ↑ Haeupler, Jampani, Lubiw, 2013, с. 147–171.
  15. ↑ Di Giacomo, Liotta, 2005.

Литература править

Thomas Bläsius, Stephen G. Kobourov, Ignaz Rutter. Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, 2013. — ISBN 9781420010268.

  • Peter Brass, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry Theory & Applications. — 2007. — Т. 36, вып. 2. — С. 117–130. — doi:10.1016/j.comgeo.2006.05.006.
  • Sergio Cabello, Marc van Kreveld, Giuseppe Liotta, Henk Meijer, Bettina Speckmann, Kevin Verbeek. Geometric simultaneous embeddings of a graph and a matching // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вып. 1. — С. 79–96. — doi:10.7155/jgaa.00218.
  • Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers. — Berlin: Springer, 2008. — Т. 4875. — С. 280–290. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-77537-9_28.
  • Jean Cardinal, Vincent Kusters. The complexity of simultaneous geometric graph embedding // Journal of Graph Algorithms and Applications. — 2015. — Т. 19, вып. 1. — С. 259–272.
  • Christian Duncan, David Eppstein, Stephen G. Kobourov. Proc. 20th ACM Symposium on Computational Geometry. — ACM, 2004. — С. 340–346. — doi:10.1145/997817.997868.
  • Emilio Di Giacomo, Giuseppe Liotta. Simultaneous embedding of outerplanar graphs, paths, and cycles // International Journal of Computational Geometry & Applications. — 2007. — Т. 17, вып. 2. — С. 139–160. — doi:10.1142/S0218195907002276.
  • Fabrizio Frati. Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18–20, 2006, Revised Papers. — Berlin: Springer, 2007. — Т. 4372. — С. 108–113. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-70904-6_12.
  • J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, Michael Schulz. Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges // Computational Geometry Theory & Applications. — 2011. — Т. 44, вып. 8. — С. 385–398. — doi:10.1016/j.comgeo.2011.02.002.
  • Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers. — Berlin: Springer, 2006. — Т. 4271. — С. 325–335. — (Lecture Notes in Computer Science). — doi:10.1007/11917496_29.
  • Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw. Testing simultaneous planarity when the common graph is 2-connected // Journal of Graph Algorithms and Applications. — 2013. — Т. 17, вып. 3. — С. 147–171. — doi:10.7155/jgaa.00289.
  • Emilio Di Giacomo, Giuseppe Liotta. 21st European Workshop on Computational Geometry. — Eindhoven University of Technology, 2005.
Источник — https://ru.wikipedia.org/w/index.php?title=Одновременное_вложение_графов&oldid=112534120