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

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

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

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

Для задач одновременного вложения более двух графов обычно предполагается, что все пары входных графов имеют одни и те же пересечения. То есть множества рёбер и вершин образуют подсолнечник^[англ.]. Это ограничение известно как пересечение подсолнуха^[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].