Edge crossing reduction in graph

Question

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.

Answer 1

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.

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.