Graphzeichnen

Grundidee und Aufgabenfeld

Graphzeichnen (englisch: Graph Drawing) ist ein Gebiet der Informatik und der Diskreten Mathematik. Es beschäftigt sich damit, Graphen geometrisch zu realisieren, also ihre abstrakte Struktur in einer räumlichen Zeichnung darzustellen. Algorithmen berechnen für einen gegebenen Graphen meist eine zweidimensionale Einbettung in den euklidischen Raum.

Die Knoten werden gewöhnlich als Punkte, Kreise oder Quadrate dargestellt. Eine Kante zwischen zwei Knoten wird durch eine Jordan-Kurve repräsentiert, die die den Knoten zugeordneten geometrischen Objekte miteinander verbindet.

Man unterscheidet zwei Aufgabenbereiche. Beim statischen Graphzeichnen wird ein einzelner Graph dargestellt. Beim dynamischen Graphzeichnen wird dagegen eine ganze Folge von Graphen visualisiert, meist in Form einer Animation. Die Verfahren müssen dabei nicht nur einzelne Zeichnungen erzeugen, sondern gegebenenfalls auch die Veränderungen zwischen den Graphen verständlich machen.

Ansätze zur Anordnung der Graphen

Es gibt keine universelle Technik, die für jeden Graphen gleichermaßen geeignet ist. Welcher Ansatz verwendet wird, hängt vom Anwendungsgebiet und vom gewünschten Darstellungseffekt ab.

Beim hierarchischen Zeichnen wird aus einem gerichteten Graphen eine Hierarchie abgeleitet. Die Knoten werden in Äquivalenzklassen eingeteilt; Knoten derselben Klasse werden auf gleicher Höhe angeordnet. Dadurch tritt die im Graphen enthaltene Hierarchie deutlich hervor. Hierarchische Graphen werden in der Geschäftsprozessmodellierung unter anderem für Wertschöpfungskettendiagramme und Organigramme genutzt.

Beim Zeichnen mit Ausrichtung am längsten Pfad werden alle Start-Knoten, also Knoten ohne Vorgänger, und End-Knoten, also Knoten ohne Nachfolger, betrachtet. Gesucht wird die Kombination aus Start- und End-Knoten, deren Pfad die größte Anzahl dazwischen liegender Knoten besitzt. Dieser längste Pfad bildet die Grundlage für die Ausrichtung: Die darin liegenden Knoten und Kanten werden möglichst auf einer Geraden angeordnet, während die übrigen Knoten und Kanten um diese Gerade herum platziert werden. Dieses Verfahren wird in der Geschäftsprozessmodellierung unter anderem für EPKs verwendet. In der Softwaremodellierung kann eine solche Darstellung in den Notationen BPMN und UML eingesetzt werden. Die automatische Berechnung solcher Layouts ist ein Problem mit erheblichem Entwicklungspotenzial.

Beim kräftebasierten Zeichnen wird angenommen, dass auf die Knoten Kräfte wirken, die sich aus den Kanten ergeben. Für jeden Knoten wird die Gesamtkraft bestimmt; aus ihr werden die Positionen der Knoten berechnet. Die Kanten werden dabei immer als gerade Linien dargestellt. Möglich sind auch komplexere mathematische oder pseudo-physikalische Modelle. Beispielsweise können sich alle Knoten gegenseitig abstoßen, ähnlich einer elektrostatischen Kraft. Alternativ können Knoten mit unterschiedlicher Dichte in einem flüssigen Medium simuliert werden und dadurch unterschiedlich starken Auftrieb erfahren. So entstehen natürlich wirkende und oft intuitiver interpretierbare Zeichnungen.

Beim skizzenbasierten Zeichnen ist bereits eine Skizze des Graphen vorhanden. Aus ihr wird eine Graphzeichnung erzeugt, wobei die Knoten ihre ursprünglichen Positionen behalten. Ein Beispiel ist die Vereinfachung von Karten in der Kartografie: Ausgewählte Orte werden als Knoten und die Straßen zwischen ihnen als Kanten dargestellt. Die Kanten verlaufen meist als gerade Linien und werden gegenseitig ausgerichtet. Solche Zeichnungen können als Anfahrtskizzen oder für Busfahrpläne dienen.

Das Spektral-Layout ist eine Klasse von Algorithmen, die Eigenvektoren einer Matrix, etwa der Laplace-Matrix, als kartesische Koordinaten verwenden. Dazu werden die zwei größten oder die zwei kleinsten Eigenwerte und die zugehörigen Eigenvektoren der Laplace-Matrix des Graphen berechnet. Normalerweise werden die Knoten in einer zweidimensionalen Ebene platziert; weitere Eigenvektoren ermöglichen Einbettungen in mehr Dimensionen. Entspricht ein Knoten der Zeile beziehungsweise Spalte i der symmetrischen Laplace-Matrix L, dann sind seine x- und y-Koordinaten im zweidimensionalen Fall die i-ten Einträge des ersten und zweiten Eigenvektors von L.

Arten von Zeichnungen

Die Art einer Zeichnung richtet sich nach dem gewünschten Ergebnis.

Bei einer orthogonalen Zeichnung werden Kanten als Polygonzüge dargestellt. Die einzelnen Liniensegmente treffen sich an Ecken und verlaufen ausschließlich horizontal oder vertikal, niemals diagonal. Organigramme sind ein Beispiel für diese Darstellungsart.

Bei einer Spline-Zeichnung werden die Kanten durch geschwungene Linien ohne Knicke dargestellt. Dies kann beispielsweise mit Bezierkurven oder B-Splinekurven erreicht werden.

Qualitätsanforderungen und dynamische Darstellung

Eine Graphzeichnung soll den Betrachter nicht verwirren, sondern die besonderen Eigenschaften des zugrunde liegenden Graphen hervorheben. Entscheidend ist deshalb die Wahl eines geeigneten Layoutalgorithmus. Eine möglichst ästhetische Darstellung hängt sowohl vom persönlichen Empfinden als auch vom Zweck der Darstellung ab.

Für die Eignung einer Zeichnung lassen sich dennoch messbare Kriterien verwenden:

• der minimale Abstand und die minimale Größe der Knoten, insbesondere abhängig von der Auflösung des darstellenden Geräts;
• der maximale Abstand und die maximale Größe der Knoten, abhängig von der Anzeigefläche;
• die Varianz der Kantenlängen und Knotengrößen, etwa ob Knoten gleich groß, nach dem goldenen Schnitt abgestuft oder beliebig groß sind;
• die Anzahl der Kantenkreuzungen;
• die Anzahl der Kantenknicke bei orthogonalen Kanten beziehungsweise der Kantenstützpunkte bei Spline-Kanten;
• der Abstand benachbarter Knoten als Maß für die freie Fläche zwischen ihnen;
• vorhandene Symmetrien, beispielsweise horizontale, vertikale, diagonale oder radiale Ausrichtungen sowie gleichartige Strukturen in Teilgraphen.

Bestimmte Graphmerkmale werden durch passende Layouts besonders sichtbar. Dazu gehören Quellen, also Knoten ohne eingehende Kanten, und Senken, also Knoten ohne ausgehende Kanten. Hierarchische Layoutalgorithmen und Algorithmen zur Ausrichtung am längsten Pfad können solche Merkmale hervorheben.

Beim dynamischen Graphzeichnen sollen aufeinanderfolgende Graphen möglichst ähnlich angeordnet bleiben. Knoten, die von einem Graphen zum nächsten erhalten bleiben, sollten möglichst ihre Position oder zumindest ihre relative Anordnung behalten, etwa die horizontale und vertikale Reihenfolge. Dahinter steht die Annahme, dass der Betrachter eine sogenannte Mental Map der Darstellung bildet. Ziel ist es, diese Mental Map über die gesamte Graphfolge zu erhalten. Der Einfluss dieser Mental Map kann von der Darstellungsform abhängen: In einer Animation sind möglicherweise mehr Änderungen leichter zu verfolgen als in einer Folge einzelner Bilder, die direkt miteinander verglichen werden.

Beim dynamischen Zeichnen wird außerdem zwischen einem Offline- und einem Online-Problem unterschieden. Beim statischen Zeichnen liegt der vollständige Graph vor. Im Offline-Fall ist die vollständige Sequenz der Graphen bekannt. Beim interaktiven Graphzeichnen, auch Online-Problem genannt, liegt dagegen jeweils nur der nächste zu zeichnende Graph vor.

Anwendungen

Graphzeichnen wird eingesetzt, um Diagramme, die auf Graphen beruhen, automatisch anzuordnen. Zu den genannten Anwendungsgebieten gehören insbesondere die Geschäftsprozessmodellierung und die Softwaremodellierung. Autolayout-Algorithmen zur Erstellung solcher Zeichnungen sind auch Bestandteil spezialisierter kommerzieller Softwarebibliotheken.

Die Softwareanwendung yEd bietet umfangreiche Unterstützung für hierarchisches, kräftebasiertes und skizzenbasiertes Zeichnen. Sie ermöglicht sowohl statisches als auch dynamisches Graphzeichnen.