最小化图中的交叉边
我正在使用networkx（一个python图形绘制包）http://networkx.lanl.gov/index.html我的项目之一。虽然networkx很酷，但由于交叉边缘的数量，显示功能有点糟糕。有没有办法最小化图中的交叉边？我的意思是一种可以以最小化交叉边的方式对节点进行排序的算法？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
确定最小化交叉数量的平面图布局是 NP 困难的。请参阅 交叉号码 上的 wiki 页面。
你可以尝试一些启发式方法，我相信基于力的布局非常流行（graphviz 使用它们，如果我没记错的话）。
您还可以尝试一些近似算法，您应该在我链接的维基页面上找到参考资料。
希望有帮助。
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.