图中的边缘交叉减少 [英] Edge crossing reduction in graph

问题描述

是否有任何算法可以最小化图中的边交叉?例如，如果我有一个图的转换矩阵.

Are there any algorithms to minimize edge crossings in a graph? For example if I have a transition matrix of the graph.

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

I found methods like trying to place the nodes around the other node, but I'd like to know some other ideas.

推荐答案

已经为图形绘制应用程序开发了一系列完善的算法/库，您可以了解一些背景此处.

There's a range of well established algorithms/libraries that have been developed for graph drawing applications, you can get a bit of background here.

要绘制无向图，一个流行的选择是基于力的布局算法，其中将图边缘视为弹簧(吸引力)，而将顶点视为带电粒子(施加排斥力).该算法的工作原理是根据这些力更新顶点位置，直到达到稳定状态.您可以在此处阅读有关基于力的方法的更多信息.由于这些算法寻找平衡解决方案，因此它们通常会导致伪最佳布局，而不会出现太多边缘缠结.

To draw undirected graphs a popular choice is the force-based layout algorithm, in which graph edges are treated as springs (attractive forces) while the vertices are treated like charged particles (applying repulsive forces). The algorithm works by updating the vertex positions based on these forces until a steady-state is reached. You can read more about force based methods here. Since these algorithms search for an equilibrium solution they often result in pseudo-optimal layouts, without much edge tangling.

您可能对使用众多可用的图形绘制库之一感兴趣.Graphviz 包通常非常好，支持针对不同图形绘制应用程序的多种不同算法.

You might be interested in making use of one of the many graph drawing libraries that are available. The Graphviz package is generally pretty good and supports a number of different algorithms for different graph drawing applications.

这篇关于图中的边缘交叉减少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！