Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen

Übersichtliche graphische Visualisierungen komplexer Zusammenhänge spielen eine zentrale Rolle in zahlreichen Anwendungen sowohl innerhalb der Informatik, wie z.B. bei der Animation von Algorithmen, Visualisierung von Rechnernetzen oder Datenbankschemata, als auch außerhalb der Informatik, wie z.B. die Verbildlichung von Reaktionsvorgängen in der Chemie oder PERT-Diagramme in den Wirtschaftswissenschaften. In der Regel können solche Anwendungen als das Problem des Zeichnens gerichteter oder ungerichteter Graphen (im Sinne der Graphentheorie) modelliert werden. Es gelingt häufig, die geforderten Eigenschaften der Zeichnung in Form von Bedingungen wie Planarität bzw. Minimierung von Kreuzungen auszudrücken. Schwer spezifizierbare ästhetische Wünsche können oft ebenfalls befriedigend modelliert werden, wie z.B. als energieminimale Lösungen unter Kräftemodellen oder durch die interaktive Anwendung von graphischen Regeln.Der Entwurf, die Analyse und Implementierung geeigneter Algorithmen ist bislang noch kaum entwickelt, teilweise begründet durch die Modernität der graphikfähigen Computerhardware, die Voraussetzung für unser Projekt ist. Aufbauend auf Vorarbeiten, die teilweise von den beteiligten Wissenschaftlern durchgeführt wurden, sollen solche Algorithmen entworfen, analysiert, implementiert und in realen Anwendungen experimentell evaluiert werden. Endziel ist ein Softwarepaket, dessen Qualität gemäß Akzeptanz diverser Anwender beurteilt werden kann.

DFG-Verfahren Schwerpunktprogramme

Teilprojekt zu SPP 731:  Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen

Internationaler Bezug Österreich

Beteiligte Person Professor Dr. Stefan Näher