平面圖佈局

佈局圖時，一些邊重疊最小化技術是什麼？（最好與GraphViz相關）也有任何現有的軟件可以平面佈局圖形嗎？平面圖佈局

當前佈局 - http://www.evecakes.com/doodles/master.gif

在左上角的粉色款看起來很好，而淡藍色的部分有一些可以避免的邊緣重疊。

來源

2010-02-27 jameszhao00

你想知道如何優化graphviz的輸出或如何實現自己的邊重疊最小化？ – 2010-02-27 16:27:45

大多數前者，但我也對後者感興趣。 – jameszhao00 2010-02-27 16:54:59

我做了一些更多的研究，對於我的尺寸圖，多尺度佈局是唯一的選擇。所以目前我正在考慮SFDP。一個重要的SFDP屬性是級別，它定義了您想要的數量。 – jameszhao00 2010-02-27 20:32:57

對於一般圖，確定具有最小邊交叉的圖的平面佈局（Crossing Number）的問題是NP難的。因此使用了一些啓發式方法（如Force based layout算法）。

下面的頁面簡要描述了graphviz算法，並提出了一些使用它們的好處。它也有鏈接，其中應包含關於算法的詳細信息的PDF文件：

http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

希望有所幫助。

來源

2010-02-27 19:06:07

鏈接已損壞。 – 2016-09-10 05:52:50

如果一個圖是平面的，那麼你可以生成一個具有零邊交叉的嵌入（因爲這是一個平面圖的定義） - 確定一個圖是平面的可以通過線性的'O（N）'time [[1] （https://archive.org/details/PlanarityTestingByPathAddition）[2]（https://dl.acm.org/citation.cfm?id=321852）]，它是一個小（也是'O（N）' ）步驟來生成嵌入。對於非平面圖，是的，用最小的邊交叉來生成嵌入是NP難的，但它不能是平面嵌入/佈局。 – MT0 2017-10-11 22:12:12

以下開源Java庫有一些算法可能有助於鋪平平面圖。 http://open.trickl.com/trickl-graph/index.html

特別地，以下類提供解決問題的解析解：

ChrobakPayneLayout（基於升壓C++由Aaron溫莎實現） http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout（基於錨傳感器網絡中的免費分佈式本地化 * Nissanka B. Priyantha，Hari Balakrishnan，Erik Demaine和Seth Teller）

你可能想要做的就是使用類似這樣的東西作爲第一個「嘗試」，確保沒有重疊，儘管可能看起來不太好。然後，您可以應用強制導向的算法來更公平地分隔節點。

不幸的是，圖書館只是剛剛發佈，所以文檔很短。通過提供一些實際的代碼而不僅僅是理論，它可能是有用的。

來源

2011-12-07 16:15:49

回答

相關問題