图中的边缘交叉减少

Question

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

我发现像尝试将节点放在其他节点周围的方法，但我想知道一些其他的想法。谢谢。

Answer 1

有一系列已经建立的图形绘制应用程序已经建立的算法/库，你可以得到一些背景here。

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

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