平面图布局 [英] Planar Graph Layouts

问题描述

什么是一些边缘重叠最小化技术铺设的曲线图？ （preferably有关GraphViz的）亦是否有任何现有的软件，可以在一个平面方式布置的图

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?

目前的布局 - 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.

推荐答案

对于一般图，一个确定的图形的平面布局，至少边渡（的的交叉数）是NP难。因此，一些启发式方法被使用（如力为基础的布局算法）。

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).

下面简要的页面描述了graphviz的算法，并提出了一些方法来使用他们的利益。它也有链接，应包含有关算法的详细信息的PDF文件：

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:

<一个href="http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html">http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

希望有所帮助。

这篇关于平面图布局的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！