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?

Have you tried Graphviz for your drawing? It might do better at minimizing crossings (especially Dot if you have the kind of graphs that it prefers). What kind of graph do you have (i.e., where does it come from)? — Jeremiah Willcock, Feb 20 '11 at 16:13
I thought networkx uses graphviz for displaying (through pydot). These graphs are from traces of special type of networks. Rings are the worst-hit :( — Anil Katti, Feb 20 '11 at 16:25
possible duplicate of [Planar Graph Layouts](http://stackoverflow.com/questions/2347748/planar-graph-layouts) — Dr. belisarius, Feb 20 '11 at 16:25

score 3 · Accepted Answer · answered Feb 20 '11 at 16:16

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.

Minimize Cross Edges in a Graph

1 Answers1