Planar Graph Drawing

Lade...
Vorschaubild
Dateien
martin_mader.pdf
martin_mader.pdfGröße: 1.31 MBDownloads: 597
Datum
2008
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Masterarbeit/Diplomarbeit
Publikationsstatus
Published
Erschienen in
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].

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
020 Bibliotheks- und Informationswissenschaft
Schlagwörter
Graph Drawing
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690MADER, Martin, 2008. Planar Graph Drawing [Master thesis]
BibTex
@mastersthesis{Mader2008Plana-5838,
  year={2008},
  title={Planar Graph Drawing},
  author={Mader, Martin}
}
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#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5838">
    <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:creator>Mader, Martin</dc:creator>
    <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/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5838/1/martin_mader.pdf"/>
    <dc:contributor>Mader, Martin</dc:contributor>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5838/1/martin_mader.pdf"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen