Круговое расположение
Круговое расположение — стиль визуализации графов, при котором вершины графа располагаются на окружности, часто располагаясь равномерно, так, что они образуют вершины правильного многоугольника.
Применение
Круговое расположение хорошо подходит для сетевых топологий связи, таких как звезда или кольцоШаблон:Sfn, а также для циклических частей метаболических сетейШаблон:Sfn. Для графов с известным гамильтоновым циклом круговое расположение позволяет отразить цикл в виде окружности; такое круговое расположение образует базис для LCF-кода гамильтоновых кубических графовШаблон:Sfn.
Круговое расположение может быть использовано для визуализации полного графа, но также может быть использовано для фрагментов, таких как кластеры вершин графа, его двусвязные компонентыШаблон:SfnШаблон:Sfn, кластеры генов в графе взаимодействия геновШаблон:Sfn или естественные подгруппы в социальной сетиШаблон:Sfn. Используя несколько окружностей с вершинами графов, можно применять и другие методы расположения кластеров, такие как силовые алгоритмы визуализацииШаблон:Sfn.
Преимущество кругового расположения в таких областях, как биоинформатика или визуализация социальных сетей, заключается в его визуальной нейтральностиШаблон:Sfn — при расположении всех вершин на равном расстоянии друг от друга и от центра рисунка ни один из узлов не занимает привилегированное централизованное положение. Это важно, так как имеется психологическая тенденция воспринимать близкие к центру узлы как более важныеШаблон:Sfn.
Стиль рёбер
Рёбра на изображении графа могут представлять собой хорды окружностиШаблон:Sfn, круговые дугиШаблон:Sfn (возможно, перпендикулярные окружности в точке, так что рёбра модели располагаются как прямые в модели Пуанкаре гиперболической геометрии) или другие типы кривых Шаблон:Sfn.
Визуальное различие между внутренней и внешней частями окружности в круговом расположении может быть использовано для разделения двух типов изображения рёбер. Например, алгоритм кругового рисования Ганснера и КоренаШаблон:Sfn использует группировку рёбер внутри окружности вместе с некоторыми несгруппированными рёбрами вне окружностиШаблон:Sfn.
Для кругового расположения регулярных графов с рёбрами, нарисованными внутри и вне окружности как Шаблон:Не переведено 5, Шаблон:Не переведено 5 (угол с касательной в точке) с обеих сторон дуги одинаковы, что упрощает оптимизацию углового разрешения рисункаШаблон:Sfn.
Число пересечений
Некоторые авторы изучают задачу нахождения перестановки вершин кругового расположения, которое минимизирует число пересечений, когда все рёбра рисуются внутри окружности. Это число пересечений равно нулю только для внешнепланарных графовШаблон:SfnШаблон:Sfn. Для других графов оно может быть оптимизировано или сокращено отдельно для каждой двусвязной компоненты графа перед формированием решения, поскольку такие компоненты могут быть нарисованы без взаимодействия друг с другомШаблон:Sfn.
В общем случае минимизация числа пересечений является NP-полной задачейШаблон:Sfn, но она может быть аппроксимирована с коэффициентом , где n равно числу вершинШаблон:Sfn. Разработаны также эвристические методы сокращения сложности, например, основанные на продуманном порядке вставки вершин и на локальной оптимизацииШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
Круговое расположение может быть использовано также для максимизации числа пересечений. В частности, выбор случайной перестановки для вершин приводит к тому, что пересечение происходит с вероятностью 1/3, так что ожидаемое число пересечений может быть втрое больше максимального числа пересечений среди всех возможных расположений вершин. Дерандомизация этого метода даёт детерминированный аппроксимационный алгоритм с коэффициентом аппроксимации, равным трёмШаблон:Sfn.
Другие критерии оптимальности
Также к задачам кругового расположения относятся оптимизация длины рёбер кругового расположения, углового разрешения пересечений или ширины разреза (максимального числа рёбер, которые соединяют дуги окружности с противоположными)Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn; многие из этих задач NP-полныШаблон:Sfn.
См. также
- Хордовая диаграмма — концепция визуализации информации, тесно связанная с круговым расположением.
- Шаблон:Не переведено 5 — компьютерная игра, в которой игрок должен передвигать вершины случайно сгенерированного планарного графа с круговым расположением, чтобы распутать рисунок.