平面图布局

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库具有几个算法，可能有助于列出平面图。http://open.trickl.com/trickl-graph/index.html

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

Chrobakpaynelayout （基于亚伦·温莎（Aaron Windsor）的提升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）

您可能想做的就是将类似的事情用作第一个“尝试”，尽管看起来不太好，但可以确保没有重叠。然后，您可以应用一个以力为导向的算法来更公平地散布节点。

不幸的是，图书馆才刚刚发布，因此文档缺乏。但是，通过提供一些实际的代码而不仅仅是理论，它可能很有用。