Главная
Дуговая диаграмма — это стиль представления графа, в котором вершины располагаются вдоль прямой на евклидовой плоскости, а рёбра рисуются в виде полуокружностей на одной из двух полуплоскостей, либо в виде гладких кривых, образованных полуокружностями. В некоторых случаях отрезки прямой также используются для представления рёбер графа, если они соединяют соседние вершины на прямой.
Название «дуговая диаграмма» для такого представления графов является преемником использования аналогичного типа диаграмм Ваттенберга, которые он использовал для визуализации повторяющихся фрагментов строк, соединяя пары одинаковых подстрок. Тем не менее, сам стиль представления графа много старше названия и датируется работами Саати и Никольсона, которые использовали дуговые диаграммы для изучения числа пересечений графов. Более старое, но менее используемое название дуговых диаграмм —линейное вложение.
Хир, Босток и Огиветски написал, что дуговые диаграммы «не могут выражать полной структуры графа так же эффективно, как это делает двумерное представление», но позволяет проще представить многомерные данные, связанные с вершинами графами.
Планарные графы
Как заметил Никольсон, любое вложение графа в плоскость может быть преобразовано в дуговую диаграмму без изменения числа пересечений. В частности, любой планарный граф имеет планарную дуговую диаграмму. Однако такое вложение может потребовать использования более одной полуокружности для рисования некоторых рёбер графа.
Если граф нарисован без пересечений дуг в виде дуговой диаграммы, в которой каждое ребро представлено одной полуокружностью, рисунок является двустраничным книжным вложением, что возможно только для подгамильтоновых графов, подмножества планарных графов. Например, максимальный планарный граф имеет такое вложение тогда и только тогда, когда он содержит гамильтонов цикл. Таким образом, негамильтонов максимальный планарный граф, такой как граф Голднера–Харари, не может иметь планарного вложения с одной полуокружностью на ребро. Проверка, имеет ли данный граф дуговую диаграмму без пересечений этого типа (или, эквивалентно, книжная толщина графа равна двум), является NP-полной задачей.
Однако любой планарный граф имеет дуговую диаграмму, в которой каждое ребро представлено в виде бидуги, состоящей не более чем из двух полуокружностей. Более строго, любой st-планарный ориентированный граф (планарный направленный ациклический граф с одним источником и одним стоком, оба на внешней грани) имеет дуговую диаграмму, в которой любое ребро образует монотонную кривую, все кривые (рёбра) направлены в одну сторону. Для неориентированных планарных графов одним из способов построения дуговой диаграммы максимум с двумя полуокружностями на ребро является разделение графа и добавление дополнительных рёбер с целью получить гамильтонов цикл (при этом рёбра делятся максимум на две части), затем используется порядок вдоль гамильтонова цикла в качестве порядка следования вершин на прямой.
Минимизация пересечений
Поскольку проверка, имеет ли данный граф дуговую диаграмму без пересечений с одной полуокружностью на ребро, является NP-полной задачей, является также NP-трудной задачей поиск дуговой диаграммы, минимизирующей число пересечений. Задача минимизации числа пересечений остаётся NP-трудной для непланарных графов, даже если порядок вершин вдоль прямой уже задан. Однако, в случае заданного порядка вершин, вложение без пересечений (если таковое существует) может быть найдено за полиномиальное время путём перевода задачи в задачу 2-выполнимости, в которой переменные представляют расположение каждой дуги, а ограничения предотвращают расположение двух пересекающихся рёбер по одну сторону от прямой с вершинами. Кроме того, в случае фиксированного расположения вершин вложение с минимизацией числа пересечений может быть аппроксимировано путём решения задачи максимального разреза во вспмогательном графе, который представляет полуокружности и их потенциальные пересечения.
Кимиковский, Шоуп, Хе, Сикора и Врто обсуждали эвристические алгоритмы поиска дуговых диаграмм с несколькими пересечениями.
Ориентация по часовой стрелке
Для представления ориентированных графов общим соглашением является направление дуг по часовой стрелке, так что дуги, направленные слева направо, рисуются над прямой, а дуги справа налево рисуются под прямой. Это соглашение об ориентации по часовой стрелке разрабатывалось как часть другого стиля представления графа группой, в которую входили Фекете, Ванг, Данг и Арис, а к дуговым диаграммам этот стиль применили Преториус и ван Вейк.
Другое использование
Дуговые диаграммы использовал Брандес для визуализации диаграмм состояний сдвигового региста, а также Джиджев и Врто для доказательства, что число пересечений любого графа по меньшей мере равно квадрату его ширины разреза.