zum Inhalt springen

Vorlesung "Automatisches Zeichnen von Graphen"

Dozent: Prof. Dr. Michael Jünger

Mo 10-11:30 Uhr im HS 301 Pohligstr. 1
Mi 10-11:30 Uhr im HS 301 Pohligstr. 1

"Automatisches Zeichnen von Graphen" ist ein junges und lebhaftes Forschungsgebiet. Hier werden Algorithmen entworfen, die ästhetisch "schöne" Zeichnungen von Diagrammen (wie z.B. Flussdiagrammen, PERT-Diagrammen, ER-Diagrammen, Ereignisprozessketten, UML-Diagrammen oder Netzwerken) generieren.

Es gibt viele verschiedene Zeichenverfahren, die jeweils unterschiedliche Kriterien optimieren. Beispielkriterien für eine ästhetisch "schöne" Zeichnung sind etwa "wenige Überkreuzungen", "wenige Knicke" oder "möglichst grosse Winkel".

In der Vorlesung werden wir neben Algorithmen zum Zeichnen von allgemeinen (ungerichteten und gerichteten) Graphen auch Zeichenmethoden zum Zeichnen spezieller Graphen, wie etwa Bäume, gerichtete azyklische Graphen oder planare Graphen behandeln.

Begeitend zur Vorlesung wird ein Skriptum im Internet angeboten werden.

Literatur

  • Di Battista, G., Eades, P., Tamassia, R., Tollis, I. G., Graph Drawing: Algorithms for the visualization of graphs, Prentice Hall, New Jersey, 1999.
  • Kaufmann, M., Wagner, D. (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer Verlag, 2001.
  • Jünger, M., Mutzel, P. (eds.), Graph Drawing Software, Mathematics and Visualization, Springer Verlag, 2004.

Vermittelte Fähigkeiten

Analyse und Modellierung von Problemen, selbständige Implementierung einiger Zeichenverfahren, Einblick in die Graphentheorie und Graphenalgorithmen.

Übungen
In den Übungen wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben und Programmieraufgaben werden unter Anleitung eines Tutors besprochen. Bei erfolgreicher Teilnahme an der abschließenden Klausur kann ein Übungsschein erworben werden.