将有向无环图映射到网格/矩阵的方法

Question

我有一个包含数千个顶点和边缘的DAG.

我正在寻找能够以最友好/最美观的方式将顶点定位在网格点上的算法.我的预感是最好的布局类似于布局,边长最小.

你能指出我有效的算法来获得这种最小边长长度布局,还是能够帮助我解决这个问题的其他算法？

这是一个非常天真的算法输出的一部分:

Answer 1

我很确定这是一个悬而未决的问题（“图形绘制”）。您可能需要考虑优化的其他一些事情：

• 来自顶点的边之间的角度（最大化）
• 边缘交叉数（最小化）

您也许可以使用遗传算法或其他某种元启发式算法，但我不知道结果会有多好。