Graphzeichnen

Das Graphzeichnen (engl. Graph Drawing) ist ein Themengebiet der Informatik und der Diskreten Mathematik, das sich damit beschäftigt, Graphen geometrisch zu realisieren. Eine zentrale Rolle beim Graphzeichnen bilden Algorithmen, die für einen gegebenen Graphen eine 2-dimensionale Einbettung in den Euklidischen Raum berechnen. Die Knoten des Graphen werden in der Regel durch einfache geometrische Objekte wie Punkte, Kreise oder Quadrate realisiert. Gibt es eine Kante zwischen zwei Knoten, wird dies in der Zeichnung durch eine Jordan-Kurve dargestellt, welche die den Knoten zugeordneten Objekte verbindet.

Das Graphzeichnen ist 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.

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.

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.

In der Geschäftsprozessmodellierung werden hierarchische Graphen u. a. für Wertschöpfungskettendiagramme oder Organigramme verwendet.

Ausrichtung am längsten Pfad

Dabei wird zwischen allen Start-Knoten (Knoten ohne Vorgänger) und End-Knoten (Knoten ohne Nachfolger) diejenige Kombination ermittelt, bei der der Pfad zwischen Start- und End-Knoten die größte Anzahl dazwischen liegender Knoten aufweist. Dieser längste Pfad wird dann zur Basis für die Ausrichtung aller Knoten und Kanten, wobei die im längsten Pfad liegenden Knoten und Kanten möglichst an einer Gerade ausgerichtet werden und die nicht im längsten Pfad liegenden Knoten und Kanten um die Gerade herum angeordnet werden.

In der Geschäftsprozessmodellierung werden am längsten Pfad ausgerichtete Graphen u. a. für EPKs verwendet. Dabei ist die Anwendung von Autolayout-Algorithmen zur Berechnung eines am längsten Pfad ausgerichteten Graphen ein Problem mit erheblichem Entwicklungspotential.

In der Softwaremodellierung kann diese Darstellung in den Notationen BPMN und UML verwendet werden.

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. Darüber hinaus können komplexere mathematische oder pseudo-physikalische Modelle für die Berechnung der Kräfte angewandt werden. So können sich z. B. alle Knoten gegenseitig abstoßen (ähnlich einer elektrostatischen Kraft). Knoten können auch mit unterschiedlicher Dichte in einem flüssigen Medium simuliert werden, so dass einzelne Knoten mehr oder weniger Auftrieb erfahren. Auf diese Weise ergeben sich natürlicher anmutende und oft intuitiver interpretierbare Zeichnungen des Graphen.

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 in der Kartografie beim Vereinfachen von Karten Anwendung: Bestimmte Orte werden aus der Karte 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 Karte 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.

Spektral-Layout

Das Spektral-Layout ist eine Klasse von Algorithmen zum Zeichnen von Graphen. Es verwendet die Eigenvektoren einer Matrix, wie der Laplace-Matrix, als kartesische Koordinaten der Knoten. Dabei werden die zwei größten, oder kleinsten Eigenwerte und die dazugehörigen Eigenvektoren der Laplace-Matrix des Graphen berechnet und diese dann für die Anordnung der Knoten benutzt. Normalerweise werden die Knoten in der 2-dimensionalen Ebene platziert. Die Einbettung in mehr Dimensionen kann durch Verwenden von weiteren Eigenvektoren geschehen.

Im 2-dimensionalem Fall sind bei einem gegebenen Knoten, der der Zeile/Spalte in der (symmetrischen) Laplace-Matrix des Graphen entspricht, die - und -Koordinaten die -ten Einträge des ersten und des zweiten Eigenvektors von .

Arten von Zeichnungen

Je nach gewünschtem Ergebnis teilt man die Art der Zeichnungen in folgende Klassen ein:

Orthogonale Zeichnung

Orthogonale Verbindung von Knoten eines Graphen

Kanten sind in orthogonalen Zeichnungen immer als Polygonzüge dargestellt, die an Ecken miteinander verbunden sind. Alle Linienzugsegmente verlaufen dabei innerhalb der Zeichnung vertikal oder horizontal, aber nie diagonal. Beispiele sind u. a. Organigramme.

Spline-Zeichnung

Spline-Verbindung von Knoten eines Graphen

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 hierzu siehe

Anforderungen an Zeichnungen

Die Darstellung eines Graphen sollte auf einen Betrachter auf keinen Fall verwirrend wirken, sondern sollte die besonderen Eigenschaften des zugrundeliegenden Graphen betonen. Dabei ist die Auswahl des Algorithmus zur Berechnung der Darstellung ausschlaggebend. Dieser Algorithmus soll eine möglichst ästhetische Darstellung des Graphen realisieren. Was als möglichst ästhetische Darstellung angesehen wird ist jedoch einerseits vom persönlichen Empfinden des Betrachters und andererseits vom beabsichtigten Zweck der Darstellung abhängig. Es gibt dennoch messbare Kriterien, nach denen die Eignung der Darstellung für einen beabsichtigten Zweck beurteilt werden kann, wie

• den minimalen Abstand und die minimale Größe der Knoten, beeinflusst durch die Auflösung des darstellenden Gerätes,
• den maximalen Abstand und die maximale Größe der Knoten, beeinflusst durch die Anzeigefläche des darstellenden Gerätes,
• die Varianz der Kantenlängen und Knotengrößen (gleiche Größe, am goldenen Schnitt abgestuft, beliebige Größe),
• die Anzahl der Kantenkreuzungen,
• die Anzahl der Kantenknicke (bei orthogonalen Kanten) oder Kantenstützpunkte (bei Spline-Kanten),
• den Abstand benachbarter Knoten zueinander (als Maß für die freie Fläche zwischen zwei Knoten) oder
• Symmetrien wie horizontale, vertikale, diagonale, radiale Ausrichtung oder gleichartige Strukturen in Teilgraphen.

Eine besondere Eigenschaft von Graphen sind zum Beispiel das Vorhandensein von Quellen (Knoten ohne eingehende Kanten) oder Senken (Knoten ohne ausgehende Kanten). Diese Eigenschaft wird von einem hierarchischen Layoutalgorithmus oder einem Layoutalgorithmus zur Ausrichtung am längsten Pfad 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 oder wenigstens ihre relativen Anordnungen (horizontale und vertikale Knotenreihenfolge) 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 die gesamte Sequenz zu erhalten. Dabei kann der Einfluss der Mental Map davon abhängig auf welche Art ein dynamischer Graph gezeichnet wird. So ist es möglicherweise in einer Animation beispiel leichter, mehr Änderungen zu Folgen als bei einer Folge von Einzelbildern, in denen man aufeinanderfolgende Darstellungen vergleichen muss.

Neben der Erhaltung der Mental Map als weitere Anforderung kann man die Problemstellung beim Zeichnen dynamischen Graphen noch weiter in zwei Fälle unterscheiden. Denn während ein statischer Graph um gezeichnet werden zu können vollständig einem Algorithmus als Eingabe vorliegen muss, so kann es bei einem dynamischen Graph der Fall sein, dass stets nur der nächste zu zeichnende Graph vorliegt. Man spricht in diesem Fall vom interaktiven Graphzeichnen oder einem in diesem Online-Problem. Im Offline-Fall liegt dann die vollständige Sequenz der Graphen vor.

Anwendungen

Graphzeichnen findet Anwendung beim automatischen Anordnen von auf Graphen basierenden Diagrammtypen unterschiedlichster Art, etwa bei der Geschäftsprozessmodellierung oder der Softwaremodellierung. Die Autolayout-Algorithmen zum Erstellen der Zeichnungen finden sich auch in spezialisierten kommerziellen Software-Bibliotheken.

Software Anwendungen wie der Diagrammeditor yEd bieten umfangreiche Unterstützung für hierarchisches, kräfte- und skizzenbasiertes Zeichnen und ermöglichen sowohl statisches als auch dynamisches Graphzeichnen.

Einzelnachweise

1. (Memento vom 21. Juni 2011 im Internet Archive)
2. Found in Space — 3-dimensionale Anzeige für agile semantische Netze@1@2Vorlage:Toter Link/co-so.org (Seite nicht mehr abrufbar, festgestellt im April 2018. Suche in Webarchiven.)
3. (Memento vom 20. Mai 2005 im Internet Archive)
4. (Memento vom 13. März 2009 im Internet Archive)
5. (Memento vom 20. Mai 2005 im Internet Archive)
6. (Memento vom 13. März 2009 im Internet Archive)
7. D. Archambault, H. Purchase, B. Pinaud: Animation, Small Multiples, and the Effect of Mental Map Preservation in Dynamic Graphs. In: IEEE Transactions on Visualization and Computer Graphics. Band 17, Nr. 4, 1. April 2011, ISSN 1077-2626, S. 539–552, doi:10.1109/TVCG.2010.78 (ieee.org [abgerufen am 20. Oktober 2016]). 
8. Stephen C. North: Incremental layout in DynaDAG. In: Graph Drawing (= Lecture Notes in Computer Science). Nr. 1027. Springer Berlin Heidelberg, 1995, ISBN 978-3-540-60723-6, S. 409–418, doi:10.1007/bfb0021824 (springer.com [abgerufen am 20. Oktober 2016]). 
9. Diel, Stephan, Görg, Carsten, Kerren, Andreas: Preserving the Mental Map using Foresighted Layout. 1. Januar 2001, ISSN 1727-5296, doi:10.2312/vissym/vissym01/175-184 (eg.org [abgerufen am 20. Oktober 2016]). 
10. Beck, Fabian, Burch, Michael, Diehl, Stephan, Weiskopf, Daniel: The State of the Art in Visualizing Dynamic Graphs. 1. Januar 2014, doi:10.2312/eurovisstar.20141174 (eg.org [abgerufen am 20. Oktober 2016]). 
11. (Memento vom 29. September 2014 im Internet Archive)

Literatur

K. M. Hall. An r-dimensional quadratic placement algorithm. Manage Science, Seiten 219–229, 1970. Kenneth M. Hall: https://www.researchgate.net/publication/227443571_An_r-Dimensional_Quadratic_Placement_Algorithm. In: ResearchGate. Abgerufen am 13. April 2021 (englisch). 

Weblinks

• Das Graphzeichnen-Portal
• 21. Internationale Konferenz über Graph drawing (GD), 2013, Bordeaux, Frankreich
• 20. Internationale Konferenz über Graph drawing (GD), 2012, Redmond, Washington, USA
• 19. Internationale Konferenz über Graph drawing (GD), 2011, Eindhoven, die Niederlande
• 18. Internationale Konferenz über Graph drawing (GD), 2010, Konstanz, Deutschland
• Linkkatalog zum Thema Graphzeichnen bei curlie.org (ehemals DMOZ)