Layout of Graph Visualizations

Lade...
Vorschaubild
Dateien
255_1.pdf
255_1.pdfGröße: 6.13 MBDownloads: 557
Datum
1999
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Angaben zur Forschungsförderung (Freitext)
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

Visualisierung ist ein attraktives und effektives Mittel sowohl der Präsentation als auch der Exploration von Daten. In beiden Fällen ist das oberste Ziel die getreue Darstellung der durch die Daten repräsentierten Information in leicht verständlicher Form. Die entscheidende Aufgabe bei der Visualisierung von Graphen, also der graphischen Darstellung binärer Relationen, ist der Abgleich der räumlichen Anordnung innerhalb des Diagramms mit den strukturellen Eigenschaften des Graphen. Dieser Schritt und sein Ergebnis werden auch das Layout der Visualisierung genannt. Dabei sind so komplexe Abhängigkeiten zu berücksichtigen, daß aussagekräftige, auf objektivierten Kriterien beruhende Visualisierungen durch eine algorithmische Behandlung des Layoutproblems überhaupt erst möglich werden.Layout von Graphenvisualisierungen ist damit insbesondere ein Problem der angewandten Informatik und diskreten Mathematik, dessen Bedeutung zusammen mit dem Bedarf an Mitteln zur Analyse und Vermittlung komplexer Informationen wächWichtigstes Ergebnis dieser Arbeit sind ein vereinheitlichender Formalismus für die Modellbildung, sowie mehrere darauf beruhende Modelle und Algorithmen. Insbesondere werden aus demselben Ansatz heraus neue Modelle für Graphen entwickelt, die so unterschiedliche Dinge wie Soziale Netzwerke, dynamische WWW-Links und Fahrplangraphen von Zug- und Fährverbindungen repräsentieren. Ein bekanntes Verfahren zum Layout von Diagrammen, in denen alle Verbindungslininen achsenparallel verlaufen sollen (wie zum Beispiel in Schaltplänen häufig der Fall) wird auf dynamische Graphen verallgemeinert. Da die grundlegende Modellierung des Problems durch Netzwerkflüsse erhalten bleibt, können optimale dynamische Layouts wie im statischen Fall effizient über Flüsse minimaler Kosten bestimmt werden. Alle vorgestellten Ansätze wurden implementiert, und zahlreiche Abbildungen zeigen die erzielten Resultate.

Zusammenfassung in einer weiteren Sprache

We break down layout of graph visualizations and present several new layout models and algorithms.
Graph layout is first embedded in the context of graphical presentation. For effective graphical presentation, substance must be conveyed in an easily comprehensible way. Grounded on formal descriptions of diagrams in general, we develop a uniform framework for graph layout, including layout of dynamic graphs.
Though at the cost of efficiency, this framework lends itself to generic implementation and therefore supports rapid prototyping of layout models that can later be refined to become amenable to more efficient algorithms. Three case studies on graphs from different domains of application show the utility of our framework:
a) For social networks we develop the first layout model that explicitly combines readability criteria with exact representation of substantive variables.
b) Static spring embedder approaches are seamlessly extended to dynamic graphs.
c) Our layout model for time table graphs of European public transportation networks appears to be the first force directed edge routing strategy.
After studying barycentric layout models, which display exponentially bad spatial and angular worst case resolution, we proof the existence of locally consistent angle assignments for planar great-circle representations of triconnected planar graphs that display many desirable properties, including optimal angular resolution, but are not realizable.
In the important special case that all angles are required to be multiples of 90 degrees, network flow models do suffies to characterize layout shape. Application of our framework for dynamic graph layout to the bend-minimum orthogonal shape approach of Tamassia (1987) enables various compromises between the number of bends and layout shape modifications in order to improve interactive orthogonal layout systems.
All proposed layout models have been implemented, and a number of examples is given.

Fachgebiet (DDC)
510 Mathematik
Schlagwörter
Graphenzeichnen, Graphenalgorithmen, graph drawing, information visualization, graph algorithms, social networks
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BRANDES, Ulrik, 1999. Layout of Graph Visualizations [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Brandes1999Layou-581,
  year={1999},
  title={Layout of Graph Visualizations},
  author={Brandes, Ulrik},
  address={Konstanz},
  school={Universität Konstanz}
}
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/581">
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:07Z</dcterms:available>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:07Z</dc:date>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:format>application/pdf</dc:format>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dcterms:title>Layout of Graph Visualizations</dcterms:title>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="deu">Visualisierung ist ein attraktives und effektives Mittel sowohl der Präsentation als auch der Exploration von Daten. In beiden Fällen ist das oberste Ziel die getreue Darstellung der durch die Daten repräsentierten Information in leicht verständlicher Form. Die entscheidende Aufgabe bei der Visualisierung von Graphen, also der graphischen Darstellung binärer Relationen, ist der Abgleich der räumlichen Anordnung innerhalb des Diagramms mit den strukturellen Eigenschaften des Graphen. Dieser Schritt und sein Ergebnis werden auch das Layout der Visualisierung genannt. Dabei sind so komplexe Abhängigkeiten zu berücksichtigen, daß aussagekräftige, auf objektivierten Kriterien beruhende Visualisierungen durch eine algorithmische Behandlung des Layoutproblems überhaupt erst möglich werden.Layout von Graphenvisualisierungen ist damit insbesondere ein Problem der angewandten Informatik und diskreten Mathematik, dessen Bedeutung zusammen mit dem Bedarf an Mitteln zur Analyse und Vermittlung komplexer Informationen wächWichtigstes Ergebnis dieser Arbeit sind ein vereinheitlichender Formalismus für die Modellbildung, sowie mehrere darauf beruhende Modelle und Algorithmen. Insbesondere werden aus demselben Ansatz heraus neue Modelle für Graphen entwickelt, die so unterschiedliche Dinge wie Soziale Netzwerke, dynamische WWW-Links und Fahrplangraphen von Zug- und Fährverbindungen repräsentieren. Ein bekanntes Verfahren zum Layout von Diagrammen, in denen alle Verbindungslininen achsenparallel verlaufen sollen (wie zum Beispiel in Schaltplänen häufig der Fall) wird auf dynamische Graphen verallgemeinert. Da die grundlegende Modellierung des Problems durch Netzwerkflüsse erhalten bleibt, können optimale dynamische Layouts wie im statischen Fall effizient über Flüsse minimaler Kosten bestimmt werden. Alle vorgestellten Ansätze wurden implementiert, und zahlreiche Abbildungen zeigen die erzielten Resultate.</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:rights>terms-of-use</dc:rights>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/581/1/255_1.pdf"/>
    <dcterms:issued>1999</dcterms:issued>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/581/1/255_1.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/581"/>
  </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
June 10, 1999
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen