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. |