Planar Graph Drawing
Planar Graph Drawing
复制标题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Martin Mader
中科院分区：
文献类型：
--
作者：
Martin Mader
本论文在图形分析与绘制领域中涉及三个方面。首先，提出了基于深度优先搜索的一般双连通图三连通分支的算法。这种线性时间算法最初由Hopcroft和Tarjan [17]发表，并由Mutzel和Gutwenger [13]修正。由于原始论文难以理解，因此该算法以插图形式呈现，以便于获得重要思想。同时，对算法中的关键命题进行了陈述和证明，使其更接近算法的实际过程。其次，提出了一个简单的线性时间的双连通平面图三角剖分算法。最后，介绍了de Fraysseix，Pach和Pollack [11]的所谓“移位方法”算法的顶点加权变体。移位法是一种线性时间算法，用于在网格上生成三角形图的直线图，该网格的面积与图的顶点数成平方。对原算法进行了改进，根据顶点权值将顶点绘制成带面积的菱形。证明了改进后的算法在线性时间内仍能生成面积为顶点权和平方的直线网格图，且边不与其他顶点表示的图相交。该算法是在一个框架内绘制一类特殊的聚类图。查找三连接组件的算法是在JAVA中为yFiles图形绘制库实现的[27]。在可视化分析工具GEOMI [1]中，用JAVA实现了顶点加权移位方法。
This thesis covers three aspects in the field of graph analysis and drawing. Firstly, the depth-first-search–based algorithm for finding triconnected components in general biconnected graphs is presented. This linear-time algorithm was originally published by Hopcroft and Tarjan [17], and corrected by Mutzel and Gutwenger [13]. Since the original paper is hard to understand, the algorithm is presented with illustrations to ease getting the vital ideas. Also, the crucial proposition is stated and proven in a way which is closer to the actual proceeding of the algorithm. Secondly, a simple linear-time algorithm for triangulating a biconnected planar graph is presented. Finally, a vertex-weighted variant of the so-called “shift-method” algorithm by de Fraysseix, Pach and Pollack [11] is introduced. The shift method is a linear-time algorithm to produce a straightline drawing of triangulated graphs on a grid with an area bound quadratic in the number of vertices of the graph. The original algorithm is modified to draw vertices as diamond shapes with area according to vertex weights. It is proven that the modified algorithm still produces a straight-line grid drawing of the graph in linear time with an area bound quadratic in the sum of vertex weights, and that edges do not cross the drawings of other vertices’ representations. The algorithm is presented within a framework to draw a special class of clustered graphs. The algorithm for finding triconnected components is implemented in JAVA for the yFiles graph drawing library [27]. The vertex-weighted shift method is implemented in JAVA for the visual analysis tool GEOMI [1].