Дуговая диаграмма

Диаграмма Фарея

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

Если граф нарисован без пересечений дуг в виде дуговой диаграммы, в которой каждое ребро представлено одной полуокружностью, рисунок является двустраничным книжным вложением, что возможно только для подгамильтоновых графов, подмножества планарных графов[6]. Например, максимальный планарный граф имеет такое вложение тогда и только тогда, когда он содержит гамильтонов цикл. Таким образом, негамильтонов максимальный планарный граф, такой как граф Голднера–Харари, не может иметь планарного вложения с одной полуокружностью на ребро. Проверка, имеет ли данный граф дуговую диаграмму без пересечений этого типа (или, эквивалентно, книжная толщина графа равна двум), является NP-полной задачей[7].

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

Поскольку проверка, имеет ли данный граф дуговую диаграмму без пересечений с одной полуокружностью на ребро, является NP-полной задачей, является также NP-трудной задачей поиск дуговой диаграммы, минимизирующей число пересечений. Задача минимизации числа пересечений остаётся NP-трудной для непланарных графов, даже если порядок вершин вдоль прямой уже задан[4]. Однако, в случае заданного порядка вершин, вложение без пересечений (если таковое существует) может быть найдено за полиномиальное время путём перевода задачи в задачу 2-выполнимости, в которой переменные представляют расположение каждой дуги, а ограничения предотвращают расположение двух пересекающихся рёбер по одну сторону от прямой с вершинами[10]. Кроме того, в случае фиксированного расположения вершин вложение с минимизацией числа пересечений может быть аппроксимировано путём решения задачи максимального разреза во вспмогательном графе, который представляет полуокружности и их потенциальные пересечения[11].

Кимиковский, Шоуп[12][13], Хе, Сикора и Врто[14] обсуждали эвристические алгоритмы поиска дуговых диаграмм с несколькими пересечениями.

Для представления ориентированных графов общим соглашением является направление дуг по часовой стрелке, так что дуги, направленные слева направо, рисуются над прямой, а дуги справа налево рисуются под прямой. Это соглашение об ориентации по часовой стрелке разрабатывалось как часть другого стиля представления графа группой, в которую входили Фекете, Ванг, Данг и Арис[15], а к дуговым диаграммам этот стиль применили Преториус и ван Вейк[16].

Дуговые диаграммы использовал Брандес[17] для визуализации диаграмм состояний сдвигового региста, а также Джиджев и Врто[18] для доказательства, что число пересечений любого графа по меньшей мере равно квадрату его ширины разреза.