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

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

Круговое расположение на примере графа Хватала

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

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

Применение

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

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

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

Стиль рёбер

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

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

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

Число пересечений

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

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

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

Другие критерии оптимальности

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

См. также

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