Диаграмма дуги

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

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

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

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

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

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

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

Однако каждый планарный граф имеет дуговую диаграмму, в которой каждое ребро нарисовано как бидуга с не более чем двумя полукругами. Более строго, каждый st -планарный ориентированный граф (планарный ориентированный ациклический граф с одним источником и одним стоком, оба на внешней грани) имеет дуговую диаграмму, в которой каждое ребро образует монотонную кривую, причем все эти кривые последовательно ориентированы от один конец вершинной линии по направлению к другому. Для неориентированных плоских графов один из способов построить дуговую диаграмму с не более чем двумя полукругами на ребро — это разделить граф и добавить дополнительные ребра так, чтобы полученный граф имел гамильтонов цикл (и чтобы каждое ребро подразделялось не более одного раза). и использовать порядок вершин гамильтонова цикла как порядок вдоль прямой. В плоском графе с $n$ вершины, не более $n/2$ нужны биарки.

Минимизация пересечений

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

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

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

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

Приложения

Схема фейри

Диаграмма Фарея набора рациональных чисел представляет собой структуру, которую геометрически можно представить в виде дуговой диаграммы. В таком виде он имеет вершину для каждого числа, расположенную на числовой прямой , и полукруглое ребро над линией, соединяющей пары чисел. $p/q$ и $r/s$ (проще говоря), для которого $|ps-rq|=1$. Полукруги диаграммы можно рассматривать как линии в модели полуплоскости Пуанкаре гиперболической плоскости с вершинами, расположенными в бесконечных точках на граничной линии этой модели. Модель полуплоскости Пуанкаре имеет бесконечную точку, которая не представлена ​​​​как точка на граничной линии, общей конечной точке всех вертикальных лучей в модели, и это может быть представлено «дробью» 1/0 (неопределенной как число ), с тем же правилом определения его смежности. Диаграмма Фарея любого набора рациональных чисел представляет собой плоский граф, а диаграмма Фарея набора всех рациональных чисел образует мозаику гиперболической плоскости идеальными треугольниками .

Дуговые диаграммы или принципиальные схемы обычно используются при изучении свернутых биополимеров, таких как белки и нуклеиновые кислоты (ДНК, РНК). Биополимеры обычно представляются последовательностью их первичного мономера вдоль линии диаграммы и дугами над линией, обозначающими связи между мономерами (например, аминокислотами в белках или основаниями в РНК или ДНК), которые соседствуют в физической структуре полимера. несмотря на то, что они несмежны в порядке последовательности. Теоретическая основа топологии цепей затем обычно применяется для извлечения локальной и глобальной топологической информации, которая, в свою очередь, может быть связана с биологической функцией свернутых молекул. Когда дуги не пересекаются, расположение двух дуг будет либо параллельным (P), либо последовательным (S). Когда есть пересечения, они представляют собой то, что в топологии схемы часто называют расположением X. Статистику P, S и X можно использовать для изучения кинетики сворачивания этих полимеров.

Дуговые диаграммы использовались Брандесом (1999) для визуализации диаграммы состояний сдвигового регистра , Джиджев и Врт'о (2002) чтобы показать, что число пересечений каждого графа ограничено снизу комбинацией его ширины разреза и степеней вершин. , Бирн и др. (2007) для визуализации взаимодействия между устройствами Bluetooth , а Оуэнс и Джанкун-Келли (2013) — для визуализации дистанции игр в американском футболе . Дополнительные применения этой техники визуализации рассмотрены Нагелем и Дювалем (2013) .

Ссылки

• Бекос, Майкл А.; Кауфманн, Майкл; Кобуров, Стивен Г.; Симвонис, Антониос (2013), «Гладкие ортогональные макеты», Рисование графиков: 20-й Международный симпозиум, GD 2012 , Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7704, Springer, стр. 150–161, номер документа : 10.1007/978-3-642-36763-2_14 , ISBN.  978-3-642-36762-5 .
• Бернхарт, Фрэнк Р.; Кайнен, Пол К. (1979), «Толщина графа в книге», Журнал комбинаторной теории , серия B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 .
• Брандес, Ульрик (1999), «В поисках графа B», Рисование графика: 7-й Международный симпозиум, GD'99 , Замок Штиржин, Чешская Республика, 15–19 сентября 1999 г., Труды , Конспекты лекций по информатике, том. 1731, Спрингер, стр. 410–415, номер документа : 10.1007/3-540-46648-7_42 , ISBN.  978-3-540-66904-3 .
• Бирн, Дараг; Лавель, Барри; Джонс, Гарет Дж. Ф.; Смитон, Алан Ф. (2007), «Визуализация взаимодействия Bluetooth: сочетание диаграммы Arc и методов DocuBurst» (PDF) , в Ормероде, Томас К.; Сас, Корина (ред.), Материалы 21-й ежегодной конференции Британской группы HCI по HCI 2007: HCI... но не так, как мы его знаем - Том 2, BCS HCI 2007, Университет Ланкастера, Соединенное Королевство, 3-7 сентября 2007 , Британское компьютерное общество, стр. 129–132 .
• Кардинал, Жан; Хоффманн, Майкл; Кастерс, Винсент; Тот, Чаба Д.; Веттштейн, Мануэль (2018), «Дуговые диаграммы, перевернутые расстояния и гамильтоновы триангуляции», Вычислительная геометрия , 68 : 206–225, arXiv : 1611.02541 , doi : 10.1016/j.comgeo.2017.06.001 , MR   3715053 , S2CID   1169 465
• Чанг, Фан Р.К .; Лейтон, Фрэнк Томпсон ; Розенберг, Арнольд Л. (1987), «Вложение графиков в книги: проблема компоновки с приложениями к проектированию СБИС» (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi : 10.1137/0608002 .
• Чимиковски, Роберт (2002), «Алгоритмы для решения фиксированной задачи линейного числа пересечений», Discrete Applied Mathematics , 122 (1–3): 93–115, doi : 10.1016/S0166-218X(01)00314-6 , MR   1907825 .
• Чимиковски, Роберт; Муми, Брендан (2007), «Аппроксимация фиксированного линейного числа пересечений», Discrete Applied Mathematics , 155 (17): 2202–2210, doi : 10.1016/j.dam.2007.05.009 , MR   2360650 .
• Чимиковски, Роберт; Шоп, Пол (1996), «Алгоритм нейронной сети для задачи компоновки графа», IEEE Transactions on Neural Networks , 7 (2): 341–345, doi : 10.1109/72.485670 , PMID   18255588 .
• Джиджев, Христо; Врт'о, Имрих (2002), «Улучшенная нижняя граница для пересекающихся чисел», Рисунок графика: 9-й Международный симпозиум, GD 2001 , Вена, Австрия, 23–26 сентября 2001 г., Пересмотренные статьи , Конспекты лекций по информатике, том . 2265, Springer, стр. 96–101, номер документа : 10.1007/3-540-45848-4_8 , ISBN.  978-3-540-43309-5 .
• Эфрат, Алон; Эртен, Чесим; Кобуров, Стивен Г. (2007), «Рисование дуги окружности с фиксированным местоположением плоских графов», Журнал графовых алгоритмов и приложений , 11 (1): 145–164, doi : 10.7155/jgaa.00140 .
• Фекете, Жан-Даниэль; Ван, Дэвид; Данг, Нием; Арис, Алекс; Плезант, Кэтрин (2003), «Наложение связей графа на древовидные карты», IEEE Symp. по визуализации информации, Сборник плакатов , стр. 82–83 .
• Гилман, Джейн ; Кин, Линда (2002), «Последовательности слов и числа пересечений» (PDF) , Комплексные многообразия и гиперболическая геометрия (Гуанахуато, 2001) , Современная математика, том. 311, Провиденс, Род-Айленд: Американское математическое общество, стр. 231–249, doi : 10.1090/conm/311/05455 , MR   1940172 ; см. раздел 2.4, «Диаграммы Фарея и цепные дроби».
• Джордано, Франческо; Лиотта, Джузеппе; Мчедлидзе Тамара; Симвонис, Антониос (2007), «Вычисление восходящих топологических книжных вложений восходящих плоских орграфов», Алгоритмы и вычисления: 18-й Международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Конспекты лекций по информатике, том . 4835, Springer, стр. 172–183, номер doi : 10.1007/978-3-540-77120-3_17 , ISBN.  978-3-540-77118-0 .
• Он, Хунмей; Сикора, Ондрей; Врт'о, Имрих (2005), «Эвристика перекрестной минимизации для двухстраничных рисунков» , Электронные заметки по дискретной математике , 22 : 527–534, doi : 10.1016/j.endm.2005.06.088 .
• Хир, Джеффри; Босток, Майкл; Огиевецкий, Вадим (2010), «Экскурсия по зоопарку визуализации», Сообщения ACM , 53 (6): 59–67, doi : 10.1145/1743546.1743567 .
• Кабакчиоглу, А.; Стелла, Ал. (ноябрь 2005 г.), «Безмасштабная сеть, скрытая в коллапсирующем полимере», Physical Review E , 72 (5), 055102(R), arXiv : cond-mat/0409584 , Bibcode : 2005PhRvE..72e5102K , doi : 10.1103/physreve.72.055102 , PMID   16383674 , S2CID   29977757
• Масуда, Сумио; Накадзима, Кадзуо; Касивабара, Тосинобу; Фудзисава, Тошио (1990), «Перекрестная минимизация в линейных вложениях графов», IEEE Transactions on Computers , 39 (1): 124–127, doi : 10.1109/12.46286 , MR   1032144 .
• Нагель, Тилль; Дюваль, Эрик (2013 г.), «Визуальный обзор дуговых диаграмм» (PDF) , Плакаты VIS 2013 г. , IEEE
• Николсон, TAJ (1968), «Процедура перестановки для минимизации количества пересечений в сети», Труды Института инженеров-электриков , 115 : 21–26, doi : 10.1049/piee.1968.0004 , MR   0311416 .
• Оуэнс, Шон Гэбриэл; Джанкун-Келли, TJ (2013), «Визуализации для исследования сезона американского футбола и игровых данных» (PDF) , 1-й семинар IEEE VIS по визуализации спортивных данных , IEEE
• Преториус, AJ; ван Вейк, Дж. Дж. (2007), «Преодоление семантического разрыва: визуализация графов переходов с помощью пользовательских диаграмм», IEEE Computer Graphics and Applications , 27 (5): 58–66, doi : 10.1109/MCG.2007.121 , PMID   17913025 , S2CID   8643133 .
• Саати, Томас Л. (1964), «Минимальное количество пересечений в полных графах», Труды Национальной академии наук Соединенных Штатов Америки , 52 (3): 688–690, Бибкод : 1964PNAS ... 52 ..688S , doi : 10.1073/pnas.52.3.688 , MR   0166772 , PMC   300329 , PMID   16591215 .
• Ваттенберг, М. (2002), «Дужные диаграммы: визуализация структуры строк», Proc. Симпозиум IEEE по визуализации информации (INFOVIS 2002) , стр. 110–116, doi : 10.1109/INFVIS.2002.1173155 , ISBN  0-7695-1751-Х , S2CID   881989 .