algorithm - 图中的边交叉减少

Question

是否有任何算法可以最小化图中的边缘交叉？例如，如果我有图的转换矩阵。

我找到了尝试将节点放置在另一个节点周围的方法，但我想知道其他一些想法。

Answer 1

已经为图形绘制应用程序开发了一系列完善的算法/库，您可以在这里获得一些背景知识。

要绘制无向图，一种流行的选择是基于力的布局算法，其中图形边缘被视为弹簧（吸引力），而顶点被视为带电粒子（施加排斥力）。该算法通过根据这些力更新顶点位置来工作，直到达到稳定状态。您可以在此处阅读有关基于力的方法的更多信息。由于这些算法搜索平衡解决方案，它们通常会导致伪最优布局，而没有太多的边缘缠结。

您可能有兴趣使用许多可用的绘图库之一。Graphviz包通常非常好，并且支持针对不同图形绘制应用程序的许多不同算法。