| Literatur |
- Di Battista, Eades, Tamassia, Tollis - Graph Drawing: Algorithms for
the visualization of graphs, Prentice Hall, 1999.
- Nishizeki, Rahman - Planar Graph Drawing, Lecture Notes Series on
Computing 12, Springer, 2004.
- Tamassia - Handbook of Graph Drawing and Visualization, CRC Press, 2016.
- Jünger, Mutzel - Graph Drawing Software, Mathematics and
Visualization, Springer, 2004.
- Kaufmann, Wagner - Drawing Graphs: Methods and Models, Lecture Notes
in Computer Science 2025, Springer, 2001. |
| Lerninhalte |
Voraussetzungen: Kenntnisse in Algorithmen+Datenstrukturen, und Graphen
Beschreibung: Automatisches Zeichnen von Graphen ist ein junges und
lebhaftes Forschungsgebiet. Hier werden Algorithmen entworfen, die
ästhetisch "schöne" Zeichnungen von Diagrammen (wie beispielsweise
Fluss- und UML-Diagramme, Netzwerke oder Ereignisprozessketten)
generieren. Die Anwendungen für diese Zeichnungen reichen von der
Verbrechensbekämpfung bis hin zur Energieüberwachung. Es gibt viele
verschiedene Zeichenverfahren, die jeweils unterschiedliche Kriterien
optimieren, und oftmals werfen diese Kriterien interessante
kombinatorische Fragestellungen auf. Beispielkriterien für eine
ästhetisch "schöne" Zeichnung sind etwa wenige Überkreuzungen, wenige
Knicke oder auch möglichst große Winkel.
In dieser Vorlesung werden wir neben Algorithmen zum Zeichnen von
allgemeinen (ungerichteten und gerichteten) Graphen auch Zeichenmethoden
für spezielle Graphen wie Bäume, gerichtete azyklische Graphen oder
planare Graphen behandeln. Anwendungsbeispiele, zugehörige Software und
Aufgaben zur Eigenimplementierung ergänzen die Diskussion der Algorithmen. |
