分层图绘制

生成的有向无环图分层图]]
分层图绘制（Layered graph drawing）或层级图绘制（hierarchical graph drawing）是的一种形式。这种布局中，有向图的顶点排列在水平行或水平层中，边的方向通常自上而下。该方法最早由提出，因此又称杉山风格图绘制（Sugiyama-style graph drawing）。

分层图的理想形式是，此时所有边的方向完全一致且彼此不相交。然而，实际图结构往往包含环路，而将方向不一致的边数减至最少属于NP困难问题，使交叉数最小化同样也是NP困难问题。因此，分层图绘制系统通常采用一系列启发式算法来减少此类布局缺陷，但不保证能求得缺陷最少的全局最优解。

布局算法
构建分层图通常分为以下几个步骤：

• 若输入的图不是有向无环图，则需找出通过反转方向可使全图无环的边集。寻找最小边集属于NP完全的问题，因此通常采用贪心启发式策略代替精确优化算法。该问题的精确解可通过整数规划建模。
• 将上一步得到的有向无环图顶点分配到各层中，使每条边都由较高层指向较低层。该阶段旨在同时减少总层数、缩短跨层长边并平衡各层的顶点分配。整数规划方法虽然耗时较长，但可将边长最小化与每层顶点数限制结合求解。
• 跨越多个层级的边会被替换为由虚拟顶点构成的路径。经过此步骤后，扩展图中的每条边都只连接布局中相邻两层的顶点。
• 调整每层内部的顶点排列，以减少当前层与上一层连接边之间的交叉。例如，根据某顶点在上一层所有邻居位置的平均数或中位数来确定其横坐标，然后通过不断交换相邻顶点对来降低交叉数。此外，也可以采用一种相对于当前层与上一层之间交叉数固定参数可解的算法来决定单层顶点的顺序。
• 在保持上一步计算出的排列顺序的前提下，为每个顶点分配层内横坐标。
• 将算法第一步中反转的边恢复至原始方向，从图中移除虚拟顶点，最终绘制出完整的顶点和边。为避免顶点与边相交，跨越多层的边可绘制为通过该边上各虚拟顶点位置的折线或样条曲线。

Graphviz中的dot工具可生成分层图。和中也包含了分层图绘制算法。

变体
虽然分层图绘制算法通常将顶点排成行且边自上而下延伸，但也可以将顶点排成列且边自左向右延伸。.一种算法框架也已应用于放射状布局（图围绕某个起始节点排列在同心圆上）以及图的三维分层绘制。

在包含大量长边的分层图中，可以通过将边集分组成束并让其共同穿过同一组虚拟顶点来减少边的杂乱感。类似地，对于在连续两层之间存在大量边交叉的图，极大二分子图中的边可以分组成汇合束。

顶点按层排列的布局也可以通过不遵循杉山框架的算法来构建。例如，利用此类图具有有界径宽这一事实，可以在对任意固定的k和h呈多项式时间内，判断一个无向图是否存在最多包含k个交叉且使用h层的布局方案。

对于概念格的分层绘制，可以使用结合了杉山框架与加性方法（其中每个顶点代表一个集合，顶点位置是代表集合中元素的向量之和）的混合方法。在这种混合方法中，算法的顶点排列和坐标分配阶段被单一阶段取代，在该阶段中，每个顶点的横坐标被选为代表该顶点元素的标量之和。分层图绘制方法还用于为力导向图提供初始位置。

参考