algorithm - 平面图布局

Question

布置图时有哪些边缘重叠最小化技术？（最好与 GraphViz 相关）还有任何现有的软件可以以平面方式布局图形吗？

当前布局 - http://www.evecakes.com/doodles/master.gif

左上角的粉色部分看起来不错，而浅蓝色部分有一些可避免的边缘重叠。

Answer 1

对于一般图，确定具有最少边交叉（交叉数）的图的平面布局的问题是 NP-hard。因此使用了一些启发式方法（如基于力的布局算法）。

下面的页面简要描述了 graphviz 算法，并提出了一些使用它们的方法。它还具有指向 pdf 的链接，其中应包含有关算法的更多信息：

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

希望有帮助。

Answer 2

以下开源 Java 库有一些算法可以帮助布置平面图。 https://github.com/trickl/trickl-graph

特别是，以下类为问题提供了分析解决方案：

ChrobakPayneLayout（基于 Aaron Windsor 的 Boost C++ 实现） 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）

您可能想要做的是使用这样的东西作为第一次“尝试”，以确保没有重叠，尽管可能看起来不太好。然后，您可以应用力导向算法来更公平地分隔节点。

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