平面图布局

布局图时，一些边重叠最小化技术是什么？（最好与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

回答

相关问题