Круглая планировка

Круговая компоновка графа Хватала

Круговая схема диаграммы состояний протокола пограничного шлюза

Поэтапное построение кругового макета для Барабаши – Альберта. модели формирования социальной сети

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

Приложения

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

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

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

Стиль края

Края рисунка можно изобразить как хорды круга. как дуги окружности (возможно, перпендикулярно вершинному кругу, так что края моделируют линии модели диска Пуанкаре гиперболической геометрии ) или как другие типы кривых.

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

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

Количество пересечений

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

Шахрохи и др. (1995) описали алгоритм аппроксимации, основанный на сбалансированных разрезах или разделителях ребер, подмножествах из нескольких ребер, удаление которых разъединяет данный граф на два подграфа с примерно равным количеством вершин. После нахождения приблизительного разреза их алгоритм рекурсивно располагает два подграфа на каждой стороне разреза, не учитывая дополнительные пересечения, образованные ребрами, пересекающими разрез. Они доказывают, что количество пересечений, встречающихся в полученном макете, на графике $G$ с $n$ вершины, это $$O{\Bigl (}{\bigl (}\rho \log n{\bigr )}^{2}\cdot {\bigl (}C+\sum _{v\in V(G)}\deg(v)^{2}{\bigr )}{\Bigr )},$$где $C$ оптимальное количество пересечений и $\rho$ — коэффициент аппроксимации алгоритма сбалансированного вырезания, используемого этим методом компоновки. В их работе цитируется статья Фань Чунга и Шинг-Тунг Яу от 1994 года, в которой утверждалось, что $\rho =O(1)$, но позже выяснилось, что это ошибочное доказательство. Вместо этого лучшее приближение, известное для задачи сбалансированного разреза, имеет $\rho =O({\sqrt {\log n}})$, придавая этому алгоритму круговой компоновки аппроксимации коэффициент $O(\log ^{3}n)$ на графах, которые имеют большое количество пересечений относительно степеней их вершин .

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

Другие критерии оптимизации

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

См. также

• Диаграмма аккордов (визуализация информации) — тесно связанное понятие визуализации информации.
• Планарность — головоломка, в которой игрок должен перемещать вершины, чтобы распутать рисунок плоского графа , начиная со случайного кругового макета.

Внешние ссылки

• Движок круговой компоновки Graphviz

Ссылки

• Арора, Санджив ; Рао, Сатиш ; Вазирани, Умеш (2009), «Расширяющие потоки, геометрические вложения и разделение графов» (PDF) , Журнал ACM , 56 (2): A5:1–A5:37, doi : 10.1145/1502793.1502794 , MR   2535878 , S2CID   52151977
• Баур, Майкл; Брандес, Ульрик (2005), «Пересекающаяся редукция в круговых макетах», Ван Леувен, Ян (редактор), Теоретико-графовые концепции в информатике: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21-23 июня, 2004, Переработанные статьи , Конспекты лекций по информатике , том. 3353, Springer, стр. 332–343, номер документа : 10.1007/978-3-540-30559-0_28 .
• Беккер, Мориц Ю.; Рохас, Изабель (2001), «Алгоритм построения графа для построения метаболических путей», Bioinformatics , 17 (5): 461–467, doi : 10.1093/bioinformatics/17.5.461 , PMID   11331241 .
• Дехкорди, Хуман Рейси; Нгуен, Куан; Идс, Питер ; Хонг, Сок-Хи (2013), «Чертежи круговых графов с большими углами пересечения», Алгоритмы и вычисления: 7-й международный семинар, WALCOM 2013, Харагпур, Индия, 14–16 февраля 2013 г., Труды , Конспекты лекций по информатике, том . 7748, Springer, стр. 298–309, номер документа : 10.1007/978-3-642-36065-7_28 .
• Догрусёз, Угур; Бельвиранлы, М.; Дилек, А. (2012), «CiSE: Алгоритм компоновки устройства для внедрения круговых пружин», IEEE Transactions on Visualization and Computer Graphics , 19 (6): 953–966, doi : 10.1109/TVCG.2012.178 , hdl : 11693/21006 , ПМИД   23559509 , S2CID   14365664 .
• Догрусёз, Угур; Мэдден, Брендан; Мэдден, Патрик (1997), «Круговая компоновка в наборе инструментов Graph Layout», Рисование графиков: Симпозиум по рисованию графиков, GD '96, Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды , Конспекты лекций по информатике, том. 1190, Springer, стр. 92–100, doi : 10.1007/3-540-62495-3_40 .
• Дункан, Кристиан А.; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Нёлленбург, Мартин (2012), «Рисунки графов Ломбарди», Журнал графовых алгоритмов и приложений , 16 (1): 85–108, arXiv : 1009.0579 , doi : 10.7155/jgaa.00251 , S2CID   5000926 .
• Ганснер, Эмден Р.; Корен, Иегуда (2007), Рисование графиков: 14-й Международный симпозиум, GD 2006, Карлсруэ, Германия, 18-20 сентября 2006 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 4372, Springer, стр. 386–398, номер документа : 10.1007/978-3-540-70904-6_37 .
• Он, Х.; Сикора, Ондрей (2004), «Новые алгоритмы кругового рисования», Материалы семинара по информационным технологиям – приложения и теория (ITAT), Словакия, 15–19 сентября .
• Хуан, Вэйдун; Хонг, Сок Хи ; Идс, Питер (2007), «Эффекты правил рисования социограмм и пересечений ребер в визуализации социальных сетей», Журнал графовых алгоритмов и приложений , 11 (2): 397–429, doi : 10.7155/jgaa.00152 .
• Иранье, Флориан; Никольский, Маха; Матье, Бертран; Обер, Дэвид; Шерман, Дэвид (2005), «ProViz: визуализация и исследование взаимодействия белков», Bioinformatics , 21 (2): 272–274, doi : 10.1093/bioinformatics/bth494 , PMID   15347570 .
• Кребс, Валдис (1996), «Визуализация человеческих сетей» (PDF) , Выпуск 1.0: Ежемесячный отчет Эстер Дайсон , 2–96 .
• Мякинен, Эркки (1988), «О круговых макетах», Международный журнал компьютерной математики , 24 (1): 29–37, doi : 10.1080/00207168808803629 .
• Масуда, С.; Кашивабара, Т.; Накадзима, К.; Фудзисава, Т. (1987), «О NP-полноте проблемы компоновки компьютерной сети», Труды Международного симпозиума IEEE по схемам и системам , стр. 292–295 . Цитируется Бауром и Брандесом (2005) .
• Нгуен, Куан; Идс, Питер ; Хонг, Сок Хи ; Хуан, Вейдун (2011), «Большие углы пересечения в круговых планировках», Рисунок графика: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Springer, стр. 397–399, номер документа : 10.1007/978-3-642-18469-7_40 .
• Писански, Томаж ; Серватиус, Бриджит (2013), «2.3.2 Кубические графы и нотация LCF», Конфигурации с графической точки зрения , Springer, стр. 32, ISBN  9780817683641 .
• Шахрохи, Фархад; Сикора, Ондрей; Секели, Ласло А.; Врт'о, Имрих (1995), «Книжные вложения и числа пересечений», Теоретико-графовые концепции в информатике: 20-й международный семинар, WG '94, Хершинг, Германия, 16–18 июня 1994 г., Труды , Конспекты лекций по компьютеру Наука, том. 903, Springer, стр. 256–268, doi : 10.1007/3-540-59071-4_53 .
• Шмойс, Дэвид Б. (1997), «Проблемы вырезания и их применение для принципа «разделяй и властвуй» (PDF) , в Хохбауме, Дорит (редактор), Алгоритмы аппроксимации для NP-сложных задач , PWS Publishing, стр. 192– 235
• Шесть, Джанет М.; Толлис, Иоаннис Г. (1999a), «Круговые рисунки двусвязных графов», Разработка алгоритмов и экспериментирование: Международный семинар ALENEX'99, Балтимор, Мэриленд, США, 15–16 января 1999 г., Избранные статьи , Конспекты лекций по информатике, том. 1619, Springer, стр. 57–73, doi : 10.1007/3-540-48518-X_4 .
• Шесть, Джанет М.; Толлис, Иоаннис Г. (1999b), «Структура для круговых рисунков сетей», Рисование графиков: 7-й Международный симпозиум, GD'99, Замок Штиржин, Чешская Республика, 15–19 сентября 1999 г., Труды , Конспекты лекций по информатике , том. 1731, Springer, стр. 107–116, doi : 10.1007/3-540-46648-7_11 .
• Симеонидис, Алкивиадис; Толлис, Иоаннис Г. (2004), «Визуализация биологической информации с помощью круглых рисунков», Анализ биологических и медицинских данных: 5-й международный симпозиум, ISBMDA 2004, Барселона, Испания, 18–19 ноября 2004 г., Труды , конспекты лекций по информатике , том. 3337, Springer, стр. 468–478, номер документа : 10.1007/978-3-540-30547-7_47 .
• Вербицкий, Олег (2008), «О сложности обфускации плоских графов», Theoretical Computer Science , 396 (1–3): 294–300, arXiv : 0705.3748 , doi : 10.1016/j.tcs.2008.02.032 , MR   2412266 , S2CID   5948167 .