9.5.4.2 Automatisches Zeichnen von Graphen

Nach dem Studium von Stringkodes, dem sich die Linguistik seit der Mitte dieses Jahrhunderts sehr intensiv gewidmet hat (Kategorialgrammatiken, Generative und Transformationsgrammatiken), hat man sich in verallgemeinernden semiotischen Ansätzen auch dem Studium von Graphen und Graphgrammatiken gewidmet. Einen repräsentativen Überblick bietet hierzu der Artikel "Syntactics" im jüngst erschienenen 1. Band des Handbuchs der Semiotik. (Posner et al. 1997). Aber nicht nur die Graphen selbst sind für die Semiotik interessante Untersuchungsgegenstände, sondern auch das Problem ihrer Kommunikation. Insofern wird dieses zweite Problem auch von vielen anderen Disziplinen, in denen Graphen eine Rolle spielen, an die Bildsemiotik herangetragen. Während die Visualisierung einer Zeichenkette lediglich typographische Spezifikationen abverlangt, handelt es sich beim Visualisieren eines Graphen auf einer zweidimensionalen Zeichenebene um ein anspruchsvolles Problem, dem neuerdings eine ganze Forschungsrichtung gewidmet wird. Die Zeichenebene hat a priori nichts mit der abstrakten Struktur eines Graphen zu tun. Man muß sich daher der Frage widmen, inwiefern verschiedene Visualisierungen eine bessere oder schlechtere Weise des Verstehens dieser abstrakten Struktur anbieten.

Innerhalb des DFG-Schwerpunktprogramms "Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen" hat sich eine Arbeitsgruppe aus Mitgliedern der Universitäten Halle, Köln und Passau, sowie des Max-Planck-Instituts für Informatik in Saarbrücken gebildet, die sich mit dem Entwurf, der Analyse, der Implementierung und Evaluierung von neuen Algorithmen für ästhetisch schöne Zeichnungen von Graphen widmet. Einen guten Überblick über diese Aktivitäten bietet der Artikel von Franz J. Brandenburg et al. (1997).

Eine Klasse von Graphen, für die man bereits über etliche Zeichenalgorithmen verfügt, sind die planaren Graphen, die genau dadurch gekennzeichnet sind, daß man sie ohne Kantenüberschneidungen in der Ebene zeichnen kann. Für allgemeinere Graphen versucht man die Anzahl der unvermeidlichen Kreuzungen zu minimieren, sowie eine ausgewogene Ausnutzung der Zeichenfläche zu erreichen, was mit der Vermeidung zu kleiner Winkel zusammenhängt. Wenn die Kanten als Polygonzüge zeichnet, d.h. wenn man Knicke zuläßt, kommt es darauf an, die Anzahl der Kantenknicke zu minimieren. Seit 1994 gibt es internationale Graphdrawing Symposien, die jeweils einen internationalen Wettbewerb ausrichten, wo es darum geht, verschiedene Algorithmen beim Zeichnen eines konkreten Wettbewerbsgraphen zu testen. Die folgenden drei Graphiken in Bild 48 zeigen je Visualisierungen des Wettbewerbsgraphen von 1994.

Zeichnung des Wettbewerbsgraphen mit Eddas Algorithmus	Zeichnung des Wettbewerbsgraphen mit Sugiyamas Algorithmus
Gewinnerzeichnung des Wettbewerbsgraphen nach Mutzel und Odenthal

Bild 48. Visualisierungen des Wettbewerbsgraphen.

Ein wesentlicher Nutzen qualitativ guter automatischer Graphzeichnungen kommt im EncycloSpace zum Tragen, wenn Graphen nur erzeugt werden müssen, wenn sie tatsächlich gebraucht werden. Anstelle riesiger Datenbanken von Graphzeichnungen braucht man nur ein leistungsfähiges Graph-Zeichenprogramm.