Круговое расположение

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Круговое расположение на примере графа Хватала
Круговое расположение диаграммы состояний для протокола граничного шлюза
Последовательное построение кругового расположения для модели Барабаши — Альберт формирования социальной сети

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

Применение[править | править код]

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

Круговое расположение может быть использовано для визуализации полного графа, но также может быть использовано для фрагментов, таких как кластеры вершин графа, его двусвязные компоненты[1][4], кластеры генов в графе взаимодействия генов[5] или естественные подгруппы в социальной сети[6]. Используя несколько окружностей с вершинами графов, можно применять и другие методы расположения кластеров, такие как силовые алгоритмы визуализации[7].

Преимущество кругового расположения в таких областях, как биоинформатика или визуализация социальных сетей, заключается в его визуальной нейтральности[8] — при расположении всех вершин на равном расстоянии друг от друга и от центра рисунка ни один из узлов не занимает привилегированное централизованное положение. Это важно, так как имеется психологическая тенденция воспринимать близкие к центру узлы как более важные[9].

Стиль рёбер[править | править код]

Рёбра на изображении графа могут представлять собой хорды окружности[10], круговые дуги[11] (возможно, перпендикулярные окружности в точке, так что рёбра модели располагаются как прямые в модели Пуанкаре гиперболической геометрии) или другие типы кривых [12].

Визуальное различие между внутренней и внешней частями окружности в круговом расположении может быть использовано для разделения двух типов изображения рёбер. Например, алгоритм кругового рисования Ганснера и Корена[12] использует группировку рёбер внутри окружности вместе с некоторыми несгруппированными рёбрами вне окружности[12].

Для кругового расположения регулярных графов с рёбрами, нарисованными внутри и вне окружности как дуги[en], углы падения[en] (угол с касательной в точке) с обеих сторон дуги одинаковы, что упрощает оптимизацию углового разрешения рисунка[11].

Число пересечений[править | править код]

Некоторые авторы изучают задачу нахождения перестановки вершин кругового расположения, которое минимизирует число пересечений, когда все рёбра рисуются внутри окружности. Это число пересечений равно нулю только для внешнепланарных графов[10][13]. Для других графов оно может быть оптимизировано или сокращено отдельно для каждой двусвязной компоненты графа перед формированием решения, поскольку такие компоненты могут быть нарисованы без взаимодействия друг с другом[13].

В общем случае минимизация числа пересечений является NP-полной задачей[14], но она может быть аппроксимирована с коэффициентом , где n равно числу вершин[15]. Разработаны также эвристические методы сокращения сложности, например, основанные на продуманном порядке вставки вершин и на локальной оптимизации[16][1][10][17][13].

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

Другие критерии оптимальности[править | править код]

Также к задачам кругового расположения относятся оптимизация длины рёбер кругового расположения, углового разрешения пересечений или ширины разреза (максимального числа рёбер, которые соединяют дуги окружности с противоположными)[16][12][19][20]; многие из этих задач NP-полны[16].

См. также[править | править код]

  • Хордовая диаграмма — концепция визуализации информации, тесно связанная с круговым расположением.
  • Planarity[en] — компьютерная игра, в которой игрок должен передвигать вершины случайно сгенерированного планарного графа с круговым расположением, чтобы распутать рисунок.

Примечания[править | править код]

  1. ↑ 1 2 3 Doğrusöz, Madden, Madden, 1997.
  2. ↑ Becker, Rojas, 2001.
  3. ↑ Pisanski, Servatius, 2013.
  4. ↑ Six, Tollis, 1999b.
  5. ↑ Symeonidis, Tollis, 2004.
  6. ↑ Krebs, 1996.
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012.
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005.
  9. ↑ Huang, Hong, Eades, 2007.
  10. ↑ 1 2 3 Six, Tollis, 1999a.
  11. ↑ 1 2 Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012.
  12. ↑ 1 2 3 4 Gansner, Koren, 2007.
  13. ↑ 1 2 3 Baur, Brandes, 2005.
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987.
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995.
  16. ↑ 1 2 3 Mäkinen, 1988.
  17. ↑ He, Sýkora, 2004.
  18. ↑ Verbitsky, 2008.
  19. ↑ Nguyen, Eades, Hong, Huang, 2011.
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013.

Литература[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Круговое_расположение&oldid=123479504