平面图布局
布局图形时有哪些边缘重叠最小化技术？ （最好与 GraphViz 相关）还有现有的软件可以以平面方式布局图形吗？
当前布局 - http://www.evecakes.com/doodles/master.gif
左上角的粉色部分看起来不错，而浅蓝色部分有一些可以避免的边缘重叠。
What are some edge overlap minimization techniques when laying out a graph? (Preferably related to GraphViz) Also are there any existing software that can layout a graph in a planar fashion?
Current Layout - http://www.evecakes.com/doodles/master.gif
The pink section in the upper left hand corner looks fine while the light blue section has some avoidable edge overlaps.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于一般图，确定具有最少边交叉的图的平面布局的问题（交叉Number) 是 NP 困难的。因此使用了一些启发式方法（例如基于力的布局算法）。
下面的页面简要描述了 graphviz 算法，并建议了一些使用它们来获益的方法。它还包含 pdf 的链接，其中应包含有关算法的更多信息：
希望有帮助。
For general graphs, the problem of a determining a planar layout of a graph with least edges crossing (the Crossing Number) is NP-hard. So some heuristic methods are used (like the Force based layout algorithms).
The page below briefly describes the graphviz algorithms and suggests some ways to use them for benefit. It also has links to the pdfs which should contain more information about the algorithms:
Hope that helps.
以下开源 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（基于传感器网络中的无锚分布式定位
您可能想做的是使用类似的东西作为第一次“尝试”，以确保没有重叠，尽管可能看起来不太好。然后，您可以应用力导向算法来更公平地分配节点。
不幸的是，该库刚刚发布，因此缺乏文档。然而，通过提供一些实际代码而不仅仅是理论，它可能会很有用。
The following open source Java library has a couple of algorithms which may help in laying out planar graphs.
https://github.com/trickl/trickl-graph
In particular, the following classes provide analytic solutions to the problem:
ChrobakPayneLayout (based on the Boost C++ implementation by Aaron Windsor)
http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html
FoldFreeLayout (based on Anchor-Free Distributed Localization in Sensor Networks
What you might want to do is use something like this as the first "attempt" which ensures no overlaps, although may not look great. Then you can apply a force-directed algorithm to space out the nodes more fairly.
Unfortunately, the library has only just been released so is short on documentation. It might however be useful by providing some actual code rather than just theory.