## Planar Graph Drawing

2008
##### Open Access-VerÃ¶ffentlichung
Open Access Green
##### Publikationstyp
Masterarbeit/Diplomarbeit
Published
##### Zusammenfassung

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

##### Fachgebiet (DDC)
020 Bibliotheks- und Informationswissenschaft
Graph Drawing
##### Zitieren
ISO 690MADER, Martin, 2008. Planar Graph Drawing [Master thesis]
BibTex
@mastersthesis{Mader2008Plana-5838,
year={2008},
title={Planar Graph Drawing},
}
RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<dcterms:abstract xml:lang="eng">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.&lt;br /&gt;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].</dcterms:abstract>
<dc:rights>terms-of-use</dc:rights>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:28Z</dc:date>
<dcterms:title>Planar Graph Drawing</dcterms:title>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:issued>2008</dcterms:issued>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:28Z</dcterms:available>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5838"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dc:format>application/pdf</dc:format>
<dc:language>eng</dc:language>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
</rdf:RDF>