"Gute" Diagramme sind eine unerlässliche Arbeitshilfe. Sie veranschaulichen die Struktur von Datenbanken, visualisieren Arbeitsabläufe oder zeigen Steuerungsprozesse in Motoren. Diagramme bestehen aus Objekten und Verbindungslinien. Mit zunehmender Anzahl wird eine übersichtliche Anordnung sehr schwierig. Übersichtlichkeit wird erreicht, in dem das Kreuzen von Linien vermieden wird, die Linien möglichst kurz und wenig geknickt sind. "Automatic Graph Drawing" entwickelt Algorithmen, mit deren Hilfe diese Ziele erreicht werden. Petra Mutzel und ihr Team beschäftigen sich vorwiegend mit solchen Verfahren, die Diagramme "planar" (= kreuzungsfrei) machen, d.h. die Verbindungslinien überschneiden sich nicht. Die "Theorie der planaren Graphen" wurde über die letzten 250 Jahren entwickelt. Sie lässt sich aber nur bei solchen Diagrammen anwenden, bei denen eine kreuzungsfreie Darstellung von Objekten und Linien wirklich möglich ist. Ist das nicht der Fall, müssen mit Planarisierungsverfahren Linienkreuzungen auf das Notwendige beschränkt werden.

Planarisierungsverfahren

Abb.1 zeigt eine typische, wenig informative Grafik. Beim Planarisierungsverfahren wird im ersten Schritt versucht, durch das Weglassen möglichst weniger Verbindungslinien ein kreuzungsfreies Diagramm zu erhalten. Im Beispiel ist dies allein durch die Weglassung der Linie zwischen "Lager" und "Vertrieb" möglich (Abb.2). Im zweiten Schritt wird die Verbindung wieder eingetragen und der Kreuzungspunkt mit einem künstlichen Objekt versehen (Abb.3). Durch diesen Trick können dann konventionelle planare Zeichenverfahren angewendet werden. Ist die Zeichnung optimiert (Abb.4), kann das künstliche Objekt einfach wieder weggelassen werden (Abb.5). Der ganze Ablauf kann in <link http: www.tuwien.ac.at forschung nachrichten diagramme animation.gif _blank>dieser animierten Zeichnung (GIF, 330 kB) betrachtet werden.

Fortschritt nach dem LINUX-Prinzip

Gemeinsam mit zwei deutschen Forschergruppen entwickelte Mutzel während ihrer Tätigkeit in Saarbrücken das Softwarepaket <link http: www.mpi-sb.mpg.de agd _blank>AGD (Algorithms for Graph Drawing). Diese Algorithmen-Bibliothek steht für nicht-kommerzielle Zwecke kostenlos zur Verfügung und kann und soll auch von anderen Forschungsgruppen weiterentwickelt werden. Die Algorithmen können in gängige Zeichenprogramme einbezogen werden. Dann kann man mit dem sprichwörtlichen Mausklick die Optimierung der Diagramme am Bildschirm verfolgen. Ins Auge gefaßt wurde auch ein Open Source-Projekt. Das Prinzip, dass jedeR Quelltext weiterentwickeln kann, verhalf schon dem LINUX-System zu Erfolg.

2001: Konferenz in Wien

Vom 23. bis 26. September veranstaltet das Institut für Computergrafik und Algorithmen gemeinsam mit der Akademie der Wissenschaften die nächste internationale Konferenz zu "Graph Drawing". Diese Konferenzen finden seit 1993 jährlich statt.

Zur Person

Petra Mutzel, Jahrgang 1964, studierte von 1983 bis 1990 an der Universität Augsburg Wirtschaftsmathematik, dann Mathematik und Informatik. Bereits in ihrer Diplomarbeit "Implementierung und Analyse eines Max-Cut Algorithmus für planare Graphen" war die Forschungsrichtung erkennbar. Dies fand in ihrer Dissertation "The Maximum Planar Subgraph Problem" 1994 an der Universität Köln seine Fortsetzung. Nach einem Forschungsaufenthalt in Houston war Mutzel als Assistentin an der Freien Universität Berlin und der Universität Köln tätig. 1999 habilitierte sie am Max-Planck-Institut für Informatik in Saarbrücken und wurde an die TU Wien berufen. Petra Mutzel wurde für ihre Leistungen im Oktober 2000 von der <link http: www.alcatel.de stiftung _blank>Alcatel SEL Stiftung mit dem Forschungspreis für "Technische Kommunikation" ausgezeichnet. Der Preis ist mit 275 Tausend Schilling dotiert.

<link http: www.ads.tuwien.ac.at research graphdrawing.html _blank>Some information in Englisch