Построение многоуровневого графика

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