Layout of Graph Visualizations
Ulrik Brandes · KOPS (University of Konstanz) · 1999
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.