最小化圖中的交叉邊

我正在爲我的一個項目使用networkx（一個python圖形繪製包）http://networkx.lanl.gov/index.html。儘管networkx非常酷，但由於交叉邊緣的數量，顯示功能種類很少。有沒有一種方法可以最小化圖形中的交叉邊緣？我的意思是一個算法，可以排序節點的方式，使交叉邊緣最小化？最小化圖中的交叉邊

來源

2011-02-20 Anil Katti

您是否嘗試過繪製Graphviz？它可能會更好地減少交叉點（尤其是Dot，如果你有它喜歡的那種圖表）。你有什麼樣的圖表（即它來自哪裏）？ –

我以爲networkx使用graphviz來顯示（通過pydot）。這些圖來自特殊類型網絡的痕跡。環是最受打擊的:( –

可能重複的[平面圖佈局]（http://stackoverflow.com/questions/2347748/planar-graph-layouts） –

確定最小化交叉數量的平面圖佈局是NP-Hard。請參閱Crossing Number上的wiki頁面。

你可以嘗試一些啓發式，基於力的佈局是相當受歡迎，我相信（graphviz使用它們，如果我記得正確）。

您也可以嘗試一些近似算法，您應該在我鏈接的wiki頁上找到參考。

希望有所幫助。

來源

2011-02-20 16:16:58

最小化圖中的交叉邊

回答

相關問題