Reducing the intersection of edges in the graph

Question

I would like to ask you if there are any algorithms how to minimize border crossings in a graph, for example, if I have a graph transition matrix.

I found methods like trying to place nodes around another node, but I would like to know some other ideas. Thanks.

Answer 1

There are a number of well-established algorithms / libraries that have been developed for graphical drawing applications, you can get a little background here .

For drawing undirected graphs, a popular choice is the force-based layout algorithm, in which graph graphs are treated as springs (attractive forces), while vertices are treated as charged particles (using repulsive forces). The algorithm works by updating the positions of the vertices based on these forces until a steady state is reached. You can learn more about power methods here . Since these algorithms seek an equilibrium solution, they often lead to pseudo-optimal layouts, without much edge bending.

You may be interested in using one of the many graphics libraries available. The Graphviz package is usually pretty good and supports a number of different algorithms for different graphical applications.