平面图布局

Question

10

在布局图形时，有哪些边重叠最小化技术？（最好与GraphViz相关）此外，是否存在可以以平面方式布局图形的现有软件？

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

- jameszhao00

你想知道如何优化Graphviz的输出或者如何自己实现边缘重叠最小化吗？ - Antti Huima

主要是前者，但我也对后者感兴趣。 - jameszhao00

我进行了更多的研究，对于我的规模，多尺度布局是唯一的选择。所以目前我正在研究SFDP。一个重要的SFDP属性是级别，它定义了你想要多少个尺度。 - jameszhao00

1

原始布局gif文件已经404了 - 唉 - dland

2个回答

5

以下是一个开源的Java库，其中包含一些算法，可帮助布置平面图。特别是以下类提供了问题的解析解：

- 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的无锚分布式定位）

你可能想将其用作第一次"尝试"，以确保没有重叠，尽管可能不太美观。然后，您可以应用力导向算法来更公平地排列节点。

不幸的是，该库刚刚发布，缺乏文档。但它可能通过提供一些实际代码而不仅仅是理论而有所用处。

- Tim Gee

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

对于一般图形，确定具有最少边交叉的平面图布局（Crossing Number）的问题是NP难的。因此使用一些启发式方法（如Force based layout算法）。

下面的页面简要描述了graphviz算法，并提出了一些使用它们获取益处的方法。它还链接到应该包含有关算法的更多信息的pdf文件：

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

希望这有所帮助。