Minimize Cross Edges in a Graph

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?

---

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.

链接地址: http://www.djcxy.com/p/4980.html

上一篇: 序列化实体框架对象，保存到文件，读取和DeSerialize

下一篇: 最小化图中的交叉边