图中边的交叉减少技术

Question

7

有没有算法可以最小化图中的边交叉？例如，如果我有一个图的转移矩阵。

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

- DropDropped

1

你是在询问关于图形绘制的问题吗？也就是说，是否有一种算法可以为图G（V，E）提供良好的顶点布局（最小化边交叉等）？ - Darren Engwirda

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Darren Engwirda · Accepted Answer

有一系列已经成熟的算法/库被开发用于图形绘制应用程序，您可以在这里了解一些背景知识。

对于绘制无向图，常见的选择是基于力的布局算法，其中图边被视为弹簧（具有吸引力），而顶点则被视为带电粒子（施加排斥力）。该算法通过根据这些力更新顶点位置，直到达到稳态来工作。您可以在这里了解更多关于基于力的方法的信息。由于这些算法寻求平衡解决方案，因此它们通常会产生伪最优布局，而没有太多的边缠结。

您可能会对使用其中一个可用的图形绘制库感兴趣。 Graphviz软件包通常相当不错，并支持多种不同的算法以用于不同的图形绘制应用程序。