Диаграмма дуги - Arc diagram

Дуговая диаграмма График Гольднера – Харари. Отрезок красной пунктирной линии показывает, где этот график был разделен, чтобы сделать его гамильтоновым.

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

Использование фразы «дуговая диаграмма» для такого рода рисунков следует за использованием аналогичного типа диаграммы. Ваттенберг (2002) чтобы визуализировать шаблоны повторения в строках, используя дуги для соединения пар равных подстрок. Однако этот стиль рисования графиков намного старше своего названия и восходит к работам Саати (1964) и Николсон (1968), который использовал дуговые диаграммы для изучения числа пересечений графиков. Более старое, но реже используемое название для дуговых диаграмм - линейные вложения.[1]

Хир, Босток и Огиевецкий (2010) напишите, что дуговые диаграммы «могут не передавать общую структуру графа так же эффективно, как двухмерная компоновка», но что их компоновка позволяет легко отображать многомерные данные, связанные с вершинами графа.

Планарные графики

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

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

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

Минимизация переходов

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

Цимиковски и Шоп (1996), Цимиковский (2002), и Он, Сикора и Врт'о (2005) обсудить эвристику для поиска дуговых диаграмм с небольшим количеством пересечений.

Ориентация по часовой стрелке

Для рисунков ориентированные графы, общее соглашение состоит в том, чтобы рисовать каждую дугу по часовой стрелке, так что дуги, которые направлены от более ранней вершины к более поздней в последовательности, рисуются над линией вершин, а дуги, направленные от более поздней к более ранней вершине, рисуются ниже линия. Это соглашение об ориентации по часовой стрелке было разработано как часть другого стиля рисования графиков. Fekete et al. (2003), и примененный к дуговым диаграммам Преториус и ван Вейк (2007).

Другое использование

Дуговые диаграммы использовались Брандес (1999) визуализировать диаграмма состояний из регистр сдвига, и по Джиджев и Врт'О (2002) чтобы показать, что номер перехода каждого графа хотя бы квадратичен в своем ширина разреза.

Примечания

  1. ^ а б Masuda et al. (1990).
  2. ^ Нанесение полукругов на расположение кромок в вложениях книг уже было выполнено Бернхарт и Кайнен (1979), но явная связь дуговых диаграмм с вложениями двухстраничной книги, по-видимому, связана с Masuda et al. (1990).
  3. ^ Чанг, Лейтон и Розенберг (1987).
  4. ^ Джордано и др. (2007).
  5. ^ Bekos et al. (2013).
  6. ^ Эфрат, Эртен и Кобуров (2007).
  7. ^ Чимиковски и Мумей (2007).

Рекомендации