# Planar Graph Drawing

## Dateien zu dieser Ressource

Prüfsumme: MD5:a8cb2ba8ec56735848d3d57968f33316

MADER, Martin, 2008. Planar Graph Drawing [Master thesis]

2008 2011-03-24T16:00:28Z Planar Graph Drawing application/pdf Mader, Martin eng deposit-license 2011-03-24T16:00:28Z Mader, Martin 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.<br />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].