Дуговая диаграмма — это стиль рисования графа , в котором вершины графа располагаются вдоль линии в евклидовой плоскости , а ребра рисуются в виде полуокружностей в одной или обеих полуплоскостях, ограниченных линией, или в виде плавных кривых, образованных последовательностями полуокружностей. В некоторых случаях сегменты самой линии также допускаются в качестве ребер, если они соединяют только вершины, которые являются последовательными вдоль линии. Вариации этого стиля рисования, в которых полуокружности заменяются выпуклыми кривыми некоторого другого типа, также обычно называются дуговыми диаграммами. [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).
