Layout of Graph Visualizations
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BRANDES, Ulrik, 1999. Layout of Graph Visualizations [Dissertation]. Konstanz: University of KonstanzBibTex
@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>
