Graphzeichnen
aus Wikipedia, der freien Enzyklopädie
Das Graphzeichnen (engl. Graph Drawing) ist ein Themengebiet der Informatik, die sich damit beschäftigt, Algorithmen zu entwickeln, die Graphen auf dem Bildschirm oder auf Papier darstellen können. Graphzeichnen ist dabei in zwei Felder unterteilt: Im statischen Graphzeichnen soll ein Graph dargestellt werden, während im dynamischen Graphzeichnen ganze Sequenzen von Graphen (meist in einer Animation) visualisiert werden sollen.
Inhaltsverzeichnis |
[Bearbeiten] Ansätze
Im Graphzeichnen gibt es keine universellen Techniken, die einen Graphen zeichnen können. Je nach Anwendungsgebiet sind unterschiedliche Ansätze notwendig, die den jeweilig zu erzielenden Effekt unterstreichen. Die folgenden Erklärungen gelten sowohl für das statische, als auch für das dynamische Graphzeichnen.
[Bearbeiten] Hierarchisches Zeichnen
Hierbei versucht man aus einem gerichteten Graph eine Hierarchie auszulesen und diese dann angemessen darzustellen. Dazu wird die Knotenmenge in Äquivalenzklassen aufgeteilt, so dass Knoten einer Äquivalenzklasse auf einer Höhe gezeichnet werden. Dadurch entsteht eine Zeichnung, die die im Graph vorherrschende Hierarchie herausstellt.
[Bearbeiten] Kräftebasiertes Zeichnen
Diesem Ansatz liegt das Modell zugrunde, dass auf alle Knoten Kräfte wirken. Diese Kräfte ergeben sich in diesem Modell durch die Kanten. Anschließend bestimmt man die Gesamtkraft, die auf jeden Knoten wirkt und kann so die Positionen der Knoten in der Zeichnung erhalten. Kanten werden bei diesem Ansatz immer durch gerade Linien repräsentiert.
Weblink mit Beispielen:
[Bearbeiten] Skizzenbasiertes Zeichnen
In diesem Fall liegt bereits eine Skizze eines Graphen vor. Daraus wird dann ein Bild für den Graph erzeugt. Diese Methode findet zum Beispiel beim Vereinfachen von Landkarten Anwendung: Bestimmte Orte werden aus der Landkarte herausgefiltert und anschließend werden Straßen zwischen den ausgewählten Orten durch Kanten repräsentiert. In einer Zeichnung dieses Graphen werden dann alle Knoten an die Positionen gezeichnet, an denen sie schon in der Landkarte erschienen. Kanten verlaufen dann (meist als gerade Linien) gegenseitig ausgerichtet. Das resultierende Bild kann zum Beispiel als Anfahrtskizze oder für Busfahrpläne benutzt werden.
[Bearbeiten] Arten von Zeichnungen
Je nach gewünschtem Ergebnis teilt man die Art der Zeichnungen in folgende Klassen ein:
[Bearbeiten] Orthogonale Zeichnung
Kanten sind in orthogonalen Zeichnungen immer als Linienzüge dargestellt, die an Ecken miteinander verbunden sind. Alle Linienzugsegmente verlaufen dabei innerhalb der Zeichnung vertikal oder horizontal, aber nie diagonal.
Beispiele:
[Bearbeiten] Spline-Zeichnung
Die Kanten werden hierbei durch geschwungene Linien repräsentiert, die keine Knicke aufweisen. Dies kann zum Beispiel durch den Einsatz von Bezierkurven oder B-Splinekurven erreicht werden.
Beispiele:
[Bearbeiten] Anforderungen an Zeichnungen
Eine Graphzeichnung sollte auf einen Betrachter auf keinen Fall verwirrend wirken, sondern sollte die Eigenschaften des zugrundeliegenden Modells betonen. Dabei ist die Auswahl des Algorithmus zum Berechnen einer Zeichnung ausschlaggebend.
Eine besonderen Eigenschaften des Modells ist zum Beispiel das Vorhandensein von Quellen (Knoten ohne eingehende Kanten) oder Senken (Knoten ohne ausgehende Kanten). Diese Eigenschaft wird von einem hierarchischen Layoutalgorithmus besonders hervorgehoben.
Im dynamischen Graphzeichnen ist zusätzlich wichtig, dass aufeinanderfolgende Graphen nicht zu unterschiedlich gezeichnet werden. Knoten, die beispielsweise von einem Graph zum nächsten beibehalten werden, sollten möglichst ihre Position behalten. An dieser Stelle geht man davon aus, dass ein Graph eine sogenannte Mental Map besitzt, die von einem Betrachter meist unterbewusst wahrgenommen wird. Das Ziel ist es nun, die Mental Map über der gesamten Sequenz zu erhalten.
[Bearbeiten] Bemerkungen
Die Graphdrawing-Community ist derzeit aktiver denn je. So waren bei der Graphdrawing-Conference im Oktober 2004 weitaus mehr eingereichte Abhandlungen vertreten als in den Jahren zuvor. Derzeit liegt das Hauptaugenmerk der Forschung auf der Verbesserung von langsamen Algorithmen. Da viele Problemstellungen im Zusammenhang mit Graphzeichnen NP-vollständig sind, ist das Berechnen eines optimalen Layouts (optimal im Sinne des Zeichners) sehr langwierig. Daher versucht man, neue Algorithmen zu entwickeln, die möglichst schnell arbeiten und deren Ergebnisse trotzdem nahe an der optimalen Lösung liegen.
[Bearbeiten] Weblinks
[Bearbeiten] Software zur Graphvisualisierung
- Open-Directory-Liste (in Englisch)
- David Eppsteins Liste (in Englisch)
- Roberto Tamassias Liste (in Englisch)
- Georg Sanders Liste (in Englisch)
- Prefuse Visualization Framework (in English)
