Войти
Дуговая диаграмма графа Голднера – Харари. Сегмент красной пунктирной линии показывает, где этот граф был разделен, чтобы сделать его гамильтоновым. В чертеже графика, дуговая диаграмма - это стиль рисования графа, в котором вершины граф размещается вдоль линии на евклидовой плоскости, причем ребра изображаются как полукруги в одной из двух полуплоскостей, ограниченных линией, или как гладкие кривые, образованные последовательностями полукругов. В некоторых случаях линейные сегменты самой линии также допускаются в качестве ребер, если они соединяют только вершины, идущие подряд вдоль линии.
Использование фразы «дуговая диаграмма» для такого рода рисунков следует за использованием Wattenberg (2002) схемы аналогичного типа для визуализации шаблонов повторения в строках с использованием дуги для соединения пар равных подстрок. Однако этот стиль рисования графиков намного старше своего названия и восходит к работам Саати (1964) и Николсона (1968), которые использовали дуговые диаграммы для изучения номера пересечений графиков. Более старое, но менее часто используемое название дуговых диаграмм - линейные вложения .
Хир, Босток и Огиевецкий (2010) пишут, что дуговые диаграммы «могут не передавать общую структуру графа так же эффективно, как двухкомпонентные диаграммы. размерный макет », но именно их макет позволяет легко отображать многомерные данные, связанные с вершинами графа.
Диаграмма Фари Как заметил Николсон (1968), каждое вложение графа в плоскость можно деформировать в дуговую диаграмму без изменения числа пересечений. В частности, каждый планарный граф имеет плоскую дуговую диаграмму. Однако для этого вложения может потребоваться использовать более одного полукруга для некоторых его краев.
Если граф нарисован без пересечений с использованием дугообразной диаграммы, в которой каждое ребро представляет собой один полукруг, то рисунок представляет собой двухстраничную книгу, встраиваемую, что возможно только для субгамильтоновы графы, подмножество плоских графов. Например, максимальный планарный граф имеет такое вложение тогда и только тогда, когда он содержит гамильтонов цикл. Следовательно, негамильтонов максимальный планарный граф, такой как граф Голднера – Харари, не может иметь плоского вложения с одним полукругом на ребро. Проверка того, имеет ли данный граф дуговую диаграмму этого типа без перекрестков (или, что то же самое, имеет ли он номер страницы два), является NP-полным.
Однако каждый планарный граф имеет дуговую диаграмму, на которой нарисовано каждое ребро как дугу , содержащую не более двух полукругов. Более того, каждый st-планарный ориентированный граф (плоский ориентированный ациклический граф с одним источником и одним стоком, оба на внешней грани) имеет дуговую диаграмму, в которой каждое ребро образует монотонную кривую с все эти кривые последовательно ориентированы от одного конца вершинной линии к другому. Для неориентированных плоских графов один из способов построить дуговую диаграмму с не более чем двумя полукругами на ребро состоит в том, чтобы разделить граф и добавить дополнительные ребра, чтобы получившийся граф имел гамильтонов цикл (и чтобы каждое ребро было разделены не более одного раза), и использовать порядок вершин на гамильтоновом цикле как порядок вдоль прямой.
Потому что NP-полная проверка того, граф имеет дуговую диаграмму с одним полукругом на ребро и без пересечений, также NP-сложно найти дуговую диаграмму этого типа, которая минимизирует количество пересечений. Эта проблема минимизации пересечения остается NP-трудной для неплоских графов, даже если порядок вершин вдоль прямой фиксирован. Однако в случае фиксированного порядка вложение без пересечений (если оно существует) может быть найдено за полиномиальное время путем перевода проблемы в проблему 2-выполнимости, в которой переменные представляют размещение каждого arc и ограничения предотвращают размещение пересекающихся дуг с одной стороны от линии вершины. Кроме того, в случае фиксированного порядка вложение, минимизирующее пересечение, может быть аппроксимировано путем решения задачи максимального разреза во вспомогательном графе, который представляет полукруги и их потенциальные пересечения (или эквивалентно, аппроксимируя версию MAX2SAT экземпляра 2-выполнимости).
Cimikowski Shope (1996), Cimikowski (2002) и He, Sýkora Vrt'o ( 2005) обсуждают эвристику для поиска дуговых диаграмм с небольшим количеством пересечений.
Для чертежей ориентированных графов обычным соглашением является рисование каждой дуги по часовой стрелке, так что дуги, направленные от более ранней к более поздняя вершина в последовательности рисуется над линией вершин, а дуги, направленные от более поздней к более ранней вершине, рисуются ниже линии. Это соглашение об ориентации по часовой стрелке было разработано как часть другого стиля рисования графиков Fekete et al. (2003), и применен к дуговым диаграммам Pretorius van Wijk (2007).
Дуговые диаграммы использовались Brandes (1999) для визуализировать диаграмму состояний сдвигового регистра , а Djidjev Vrt'o (2002) показать, что число пересечения каждый граф по крайней мере квадратичен по своему.
