Minimize Cross Edges in a Graph

Question

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?

Answer 1

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.