平面图布局

Question

在布置图表时,有哪些边缘重叠最小化技术？(最好与GraphViz相关)还有哪些现有的软件能够以平面方式布局图形？

左上角的粉红色部分看起来很好,而浅蓝色部分有一些可避免的边缘重叠.

Answer 1

对于一般图,确定具有最小边交叉的图的平面布局(交叉数)的问题是NP难的.因此使用了一些启发式方法(如基于Force的布局算法).

下面的页面简要介绍了graphviz算法,并提出了一些使用它们获益的方法.它还包含指向pdfs的链接,其中应包含有关算法的更多信息:

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

希望有所帮助.

如果图是平面的，那么您可以生成零边交叉的嵌入（因为这是平面图的定义） - 确定图是否是平面可以在线性“O(N)”时间内实现 [[1]( https://archive.org/details/PlanarityTestingByPathAddition) [2](https://dl.acm.org/itation.cfm?id=321852)] 而且它很小（也是“O(N)”）生成嵌入的步骤。对于非平面图，是的，生成具有最小边交叉的嵌入是 NP 困难的，但它不能是平面嵌入/布局。 (3认同)
链接已损坏。 (2认同)

Answer 2

以下开放源Java库提供了一些算法，这些算法可能有助于布局平面图。 http://open.trickl.com/trickl-graph/index.html

特别是，以下类提供了对该问题的解析解决方案：

FoldFreeLayout（基于传感器网络中无锚的分布式本地化* Nissanka B. Priyantha，Hari Balakrishnan，Erik Demaine和Seth Teller）

您可能想要做的是将类似这样的内容用作第一个“尝试”，这可以确保没有重叠，尽管看起来可能并不好。然后，您可以应用力导向算法来更公平地隔开节点。

不幸的是，该库只是刚刚发布，因此缺少文档。但是，通过提供一些实际代码而不只是理论，可能会很有用。