Дуговая диаграмма — это стиль рисования графа , при котором вершины графа располагаются вдоль линии в евклидовой плоскости , а ребра рисуются в виде полукругов в одной или обеих полуплоскостях, ограниченных линией, или в виде гладких кривых. образованы последовательностями полукругов. В некоторых случаях сегменты самой линии также допускаются в качестве ребер, если они соединяют только вершины, расположенные последовательно вдоль линии. Вариации этого стиля рисования, в которых полукруги заменены выпуклыми кривыми другого типа, также обычно называют дуговыми диаграммами. [1]
Использование фразы «дуговая диаграмма» для такого типа рисунков следует за использованием диаграммы аналогичного типа Ваттенбергом (2002) для визуализации шаблонов повторения в строках с использованием дуг для соединения пар равных подстрок. Однако этот стиль рисования графов намного старше своего названия и восходит к работам Саати (1964) и Николсона (1968), которые использовали дуговые диаграммы для изучения числа пересечений графов . Более старое, но менее часто используемое название дуговых диаграмм — линейные вложения . [2] Совсем недавно дуговые диаграммы стали использоваться в рамках топологии цепей узлов и клубков, где они называются принципиальными диаграммами . [3]
Хир, Босток и Огиевецкий (2010) пишут, что дуговые диаграммы «могут не так эффективно передавать общую структуру графа, как двумерный макет», но их макет позволяет легко отображать многомерные данные, связанные с вершинами графа. . Применения дуговых диаграмм включают диаграмму Фарея , визуализацию теоретико-числовых связей между рациональными числами , а также диаграммы, представляющие вторичную структуру РНК , в которых пересечения диаграммы представляют собой псевдоузлы в структуре.
Как заметил Николсон (1968), каждый рисунок графа на плоскости можно деформировать в дуговую диаграмму без изменения количества ее пересечений. В частности, каждый планарный граф имеет плоскую дуговую диаграмму. Однако для этого вложения может потребоваться использовать более одного полукруга для некоторых его ребер.
Если граф нарисован без пересечений с использованием дуговой диаграммы, в которой каждое ребро представляет собой один полукруг, то рисунок представляет собой вложение в двухстраничную книгу , что возможно только для субгамильтоновых графов , правильного подмножества плоских графов. [4] Например, максимальный планарный граф имеет такое вложение тогда и только тогда, когда он содержит гамильтонов цикл . Следовательно, негамильтонов максимальный планарный граф, такой как граф Гольднера – Харари, не может иметь плоское вложение с одним полукругом на ребро. Проверка того, имеет ли данный граф дуговую диаграмму без пересечений этого типа (или, что то же самое, имеет ли он страницу номер два), является NP-полной . [5]
Однако каждый планарный граф имеет дуговую диаграмму, в которой каждое ребро нарисовано как бидуга с не более чем двумя полукругами. Более строго, каждый st -планарный ориентированный граф (плоский ориентированный ациклический граф с одним источником и одним стоком, оба на внешней грани) имеет дуговую диаграмму, в которой каждое ребро образует монотонную кривую, причем все эти кривые последовательно ориентированы от один конец вершинной линии по направлению к другому. [6] Для неориентированных плоских графов один из способов построить дуговую диаграмму с не более чем двумя полукругами на ребро — это разделить граф и добавить дополнительные ребра так, чтобы полученный граф имел гамильтонов цикл (и чтобы каждое ребро подразделялось не более один раз) и использовать порядок вершин гамильтонова цикла как порядок вдоль прямой. [7] В плоском графе с вершинами необходимо не более биарков. [8]
Поскольку NP-полна проверка того, имеет ли данный граф дуговую диаграмму с одним полукругом на ребро и без пересечений, также NP-трудно найти дуговую диаграмму этого типа, которая минимизирует количество пересечений. Эта задача минимизации пересечений остается NP-трудной для неплоских графов, даже если порядок вершин вдоль линии фиксирован. [2] Однако в случае фиксированного порядка вложение без пересечений (если оно существует) может быть найдено за полиномиальное время путем перевода проблемы в задачу 2-выполнимости , в которой переменные представляют расположение каждой дуги и ограничения не позволяют размещать пересекающиеся дуги на одной стороне от линии вершин. [9] Кроме того, в случае фиксированного порядка вложение, минимизирующее пересечение, может быть аппроксимировано путем решения задачи максимального разреза во вспомогательном графе, который представляет полукруги и их потенциальные пересечения (или, что то же самое, путем аппроксимации версии MAX2SAT 2 - пример выполнимости). [10]
Чимиковски и Шопе (1996), Чимиковски (2002) и Хе, Сикора и Врт'о (2005) обсуждают эвристику для поиска дуговых диаграмм с небольшим количеством пересечений.
При рисовании ориентированных графов общепринятым соглашением является рисование каждой дуги по часовой стрелке, так что дуги, направленные от более ранней вершины к более поздней в последовательности, рисуются над линией вершин, а дуги, направленные от более поздней вершины к более поздней. более ранние вершины рисуются под линией. Это соглашение об ориентации по часовой стрелке было разработано Фекете и др. как часть другого стиля рисования графиков. (2003) и применено к дуговым диаграммам Преториусом и ван Вейком (2007).
Диаграмма Фарея набора рациональных чисел представляет собой структуру, которую геометрически можно представить в виде дуговой диаграммы. В таком виде он имеет вершину для каждого числа, расположенную на числовой прямой , и полукруглое ребро над линией, соединяющей пары чисел и (проще говоря), для которых . Полукруги диаграммы можно рассматривать как линии в модели полуплоскости Пуанкаре гиперболической плоскости с вершинами, расположенными в бесконечных точках на граничной линии этой модели. Модель полуплоскости Пуанкаре имеет бесконечную точку, которая не представлена как точка на граничной линии, общей конечной точке всех вертикальных лучей в модели, и это может быть представлено «дробью» 1/0 (неопределенной как число ), с тем же правилом определения его смежности. Диаграмма Фарея любого набора рациональных чисел представляет собой плоский граф, а диаграмма Фарея набора всех рациональных чисел образует мозаику гиперболической плоскости идеальными треугольниками . [11]
Дуговые диаграммы или принципиальные схемы обычно используются при изучении свернутых биополимеров, таких как белки и нуклеиновые кислоты (ДНК, РНК). Биополимеры обычно представляются последовательностью их первичного мономера вдоль линии диаграммы и дугами над линией, обозначающими связи между мономерами (например, аминокислотами в белках или основаниями в РНК или ДНК), которые соседствуют в физической структуре полимера. несмотря на то, что они несмежны в порядке последовательности. Теоретическая основа топологии цепей затем обычно применяется для извлечения локальной и глобальной топологической информации, которая, в свою очередь, может быть связана с биологической функцией свернутых молекул. [12] Если дуги не пересекаются, расположение двух дуг будет либо параллельным (P), либо последовательным (S). Когда есть пересечения, они представляют собой то, что в топологии схемы часто называют расположением X. Статистику P, S и X можно использовать для изучения кинетики сворачивания этих полимеров. [13]
Дуговые диаграммы использовались Брандесом (1999) для визуализации диаграммы состояний сдвигового регистра , Джиджев и Врт'о (2002) чтобы показать, что число пересечений каждого графа ограничено снизу комбинацией его ширины разреза и степеней вершин. , Бирн и др. (2007) для визуализации взаимодействия между устройствами Bluetooth , а Оуэнс и Джанкун-Келли (2013) — для визуализации дистанции игр в американском футболе . Дополнительные применения этой техники визуализации рассмотрены Нагелем и Дювалем (2013).
