Forschungspreis für übersichtliche Diagramme
Die Wiener Professorin Dr. Petra Mutzel hat ein Verfahren entwickelt, das komplexe Diagramme "in Form" bringt.
Ein Bild sagt mehr als tausend Worte: Darum hat der Mensch wohl Diagramme erfunden, um komplizierte technische Zusammenhänge einfacher darzustellen. Doch allzuoft sehen Schaubilder aus, als hätte jemand eine Handvoll Knotenpunkte ausgeschüttet und nach dem Zufallsprinzip miteinander verbunden – allenfalls ein probates Mittel, um die Komplexität der eigenen Arbeit zu verdeutlichen und Ehrfurcht bei der Zuhörerschaft zu erzeugen.
Die Wiener Universitätsprofessorin Dr. Petra Mutzel hat sich mit ihrer Forschung genau dieser Problematik angenommen: beliebig komplexe Diagramme in eine möglichst übersichtliche, "zuschauerfreundliche" Darstellungsform zu bringen. Dabei muss niemand mehr selbst Hand anlegen, denn die aufwändige Optimierung erledigt eine am Institut für Computergrafik und Algorithmen der Universität Wien entwickelte Software. Für ihre Arbeit hat Petra Mutzel jetzt den mit 20 000 Euro dotierten Forschungspreis "Technische Kommunikation" der Alcatel SEL Stiftung für Kommunikationsforschung erhalten.
Gute Diagramme definieren die Graphenforscher anhand einer Reihe objektiver Kriterien. Eine Forderung ist etwa, dass sich möglichst wenige Verbindungslinien überschneiden. Weitere Kriterien: die Länge der Kanten (Verbindungslinien) sowie die Anzahl der Kurven innerhalb der Kanten. Für Graphen, die man ohne Kantenüberschneidungen zeichen kann (planare Graphen), existieren schon seit längerem mehrere Algorithmen, um eine kreuzungsfreie Darstellung zu erzeugen. Zudem lässt sich leicht testen, ob ein Graph planar ist oder nicht. Bei nicht planaren Graphen hingegen ist es extrem schwierig, eine Anordnung zu finden, welche die Anzahl der Kreuzungspunkte minimiert.
Daher benutzt die Gruppe um Petra Mutzel folgendes Näherungsverfahren: Zunächst entfernt man so viele Kanten aus dem gegebenen Graphen, dass man einen planeren Graphen erhält. Für diesen erzeugt man eine kreuzungsfreie Darstellung. Anschließend fügt man die Kanten wieder ein, und zwar so, dass möglichst wenige Überschneidungen entstehen. Eine Schwierigkeit dabei ist, nicht einfach nur irgendeinen planaren Graphen zu finden, sondern die Knoten so anzuordnen, dass möglichst wenige Biegungen entstehen. Ist eine solche Basisstruktur erst einmal gefunden, bleibt ein weiteres Problem zu lösen: die Kantenlängen so anzupassen, dass ein ästhetischer Eindruck entsteht. Um orthogonale Diagramme zu optimieren, also Diagramme, die nur aus horizontalen und vertikalen Linien bestehen, haben die Forscher einen neuen Algorithmus entwickelt und damit angeblich das bislang optimale Verfahren vom Thron gestoßen. (atr)
