Fachbereich Informatik

Graphenzeichnen Algorithmen

Die Visualisierung komplexer Datenmengen nimmt mit zunehmender Datenfülle einen immer bedeutenderen Platz in der Informationsverarbeitung ein. Beispiele für Einsatzmöglichkeiten sind CASE-Tools, WWW-Visualisierung, Datenbankenmanagement bzw. -modellierung, etc. -- um nur einige zu nennen.

Als besonders günstig hat es sich erwiesen, Graphen rechtwinklig darzustellen, da orthogonale Zeichnungen sowohl vom menschlichen Betrachter gut erfaßt als auch von Maschinen bearbeitet werden können.

Wir haben ein Modell entworfen, das inzwischen weltweit große Anerkennung bei Forschern auf diesem Gebiet gefunden hat, und eine Reihe von Algorithmen entwickelt, die automatische Zeichnungen produzieren. Diese Algorithmen optimieren im Rahmen der von dem Modell auferlegten Bedingungen verschiedene Gütekriterien wie z.B. die Anzahl der Knicke oder die benutzte Fläche.

Mit Implementierungen werden die angesprochenen Algorithmen auf ihre praktische Verwendbarkeit hin erprobt.

Veröffentlichungen

U. Fößmeier, M. Kaufmann: "Drawing High Degree Graphs with Low Bend Numbers", Proc. 4th Symposium on Graph Drawing (GD '95), LNCS 1011, pp. 254-266 , Springer Verlag, 1995.

U. Fößmeier, G. Kant, M. Kaufmann: "2-Visibility Drawings of Planar Graphs", Proc. 5th Symposium on Graph Drawing (GD '96), LNCS 1190, pp. 155-168, Springer Verlag, 1996.

U. Fößmeier, M. Kaufmann: "Nice Drawings of Planar Bipartite Graphs", Proc. 3rd Italian Conference on Algorithms and Complexity, LNCS 1203, Springer Verlag, pp. 122-134, 1997.

Th. Biedl, M. Kaufmann: "Area-Efficient Static and Incremental Graph Drawings", Proc. 5th European Symposium on Algorithms (ESA '97), LNCS 1284, Springer Verlag, pp. 37-52, 1997.

U. Fößmeier, M. Kaufmann: "Algorithms and Area Bounds for Nonplanar Orthogonal Drawings", Proc. 6th Symposium on Graph Drawing (GD '97), LNCS 1353, Springer Verlag, pp. 134-145, 1997.

U. Fößmeier: "Interactive Orthogonal Graph Drawing: Algorithms and Bounds", Proc. 6th Symposium on Graph Drawing (GD '97), LNCS 1353, Springer Verlag, 1997.