Menu
I am using networkx (a python graph-drawing package) http://networkx.lanl.gov/index.html for one of my project. Though networkx is pretty cool, the display function kind of sucks due to number of cross edges. Is there a way to minimize cross edges in a graph? I mean an algorithm which can sort the nodes in a way such that cross edges are minimized?
282
Cross Edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them.
First, for an undirected graph the proof is trivial since technically speaking the edges of an undirected graph are divided into only tree and back edges. Thus, there are no cross edges in an undirected graph.
A forward edge is a non-tree edge from a vertex to one of its descendants. A cross edge is an edge from a vertex u to a vertex v such that the subtrees rooted at u and v are distinct. A back edge is an edge from a vertex to one of its ancestors.
I had this same question...and the answer is that there are no cross edges in the BFS, but that the BFS tree itself encodes all the edges that would have been back-edges and forward-edges in the DFS tree as tree edges in the BFS tree, such that the remaining edges which the undirected graph has, but which are still not ...
Determining a planar graph layout which minimizes the number of crossings is NP-Hard. See the wiki page on Crossing Number.
You could try some heuristics, force based layout are quite popular I believe (graphviz uses them, if I recollect correctly).
You could also try some approximation algorithms, you should find references on the wiki page I linked.
Hope that helps.
177
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
