Menu
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.
594
(definition) Definition: Two different edges cross in a graph drawing if their geometric representations intersect. The number of crossings in a graph drawing is the number of pairs of edges which cross.
Definitions. For the purposes of defining the crossing number, a drawing of an undirected graph is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints.
Definition: The crossing number of a graph G, denoted cr(G), is the minimum number of crossings in any simple drawing of G. ▶ So if G is planar, cr(G) = 0, and if G is non-planar, cr(G) ≥ 1. ▶ To prove cr(G) = 1: ▶ Prove G is non-planar (Kuratowski or otherwise) and ▶ Find a drawing of G with only one crossing.
The crossing graph for such a drawing is the simple graph whose nodes correspond to the edges of G and in which two nodes are adjacent if and only if the corresponding edges cross. Example.
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.
122
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
