Построение многоуровневого графика
- Построение многоуровневого графа — это тип построения графа с горизонтальными рядами или слоями вершин и ребер.
- Идеальной формой для многослойного рисунка является направленный вверх плоский рисунок с ориентированными ребрами и без пересечений.
- Графики часто содержат циклы, и минимизация количества несогласованно ориентированных ребер и пересечений является NP-сложной задачей.
- Алгоритмы многоуровневого построения графов используют последовательность эвристик для уменьшения дефектов в чертеже.
- Построение многоуровневого графического рисунка происходит в несколько этапов, включая определение набора ребер, обращение которых делает граф ациклическим.
- Распределение вершин по слоям осуществляется таким образом, чтобы создать небольшое количество слоев, несколько ребер, охватывающих большое количество слоев, и сбалансированное назначение вершин слоям.
- Ребра, охватывающие несколько слоев, заменяются контурами фиктивных вершин, чтобы уменьшить количество пересечений между ребрами.
- Вершинам внутри каждого слоя переставляются места в попытке уменьшить количество пересечений между ребрами, соединяющими его с предыдущим слоем.
- Алгоритмы построения многоуровневых графов могут требовать O (mn) времени из-за большого количества фиктивных вершин.
- Вариации алгоритмов построения многоуровневых графов включают использование столбцов и ребер, идущих слева направо, радиальные макеты и трехмерные слоистые чертежи графиков.
Полный текст статьи: