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

Question

我有一个有数千个顶点和边的 DAG。

我正在寻找能够以最人性化/最美观的方式将顶点定位在网格点上的算法。我的预感是最好的布局将类似于具有最小边长总和的布局。

您能否指出这种最小边长布局总和的有效算法，或者可以帮助我解决这个问题的其他算法？

这是一个非常幼稚的算法的部分输出：

Answer 1

我很确定这是一个未解决的问题（“绘图”）。您可能需要考虑优化的其他几件事：

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

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