Minimize Cross Graphs on a Chart

Question

I am using networkx (python graphic drawing package) http://networkx.lanl.gov/index.html for one of my projects. Although networkx is pretty cool, the display function looks crap due to the number of cross edges. Is there a way to minimize cross edges on a chart? I mean an algorithm that can sort nodes so that cross-edges are minimized?

Answer 1

The definition of a planar graph that minimizes the number of intersections is NP-Hard. See the wiki page at Number Intersection .

You can try several heuristics, the power arrangement is quite popular. I believe that (graphviz uses them, if I remember correctly).

You can also try some approximation algorithms, you should find links to the wiki page.

Hope this helps.