Algorithmen zur Visualisierung von Graphen
Sommersemester 2009
Allgemeines
- Dozent: PD Dr. Martin Nöllenburg
- Vorlesung: Wöchentlich donnerstags 14.00 - 15.30 in SR 301 (Informatikgebäude 50.34),
erstmalig am 23. April - Übung: 14-täglich dienstags 9.45-11.15 in SR 131 (Informatikgebäude 50.34),
erstmalig am 05. Mai
Aktuelles
- mögliche Sprechstundentermine zur Prüfungsvorbereitung: bis 17.8., 26.8., 17.-18.9., ab 28.9.
- [13.08.] aktualisierte Version des Vorlesungsskripts inklusive Beschreibung des Algorithmus von de Fraysseix et al. eingestellt
- Achtung: Für den Beweis von Satz 3.20 und Abschnitt 5.1.3 bitte das angegebene Zusatzmaterial beachten
Thema
Das Graphenzeichnen beschäftigt sich mit der geometrischen Repräsentation von Graphen und Netzwerken und wird durch jene Anwendungen motiviert, in denen eine Visualisierung struktureller Informationen als Graph unentbehrlich ist. Das Gebiet erstreckt sich von rein theoretischen Aspekten bis hin zu Implementationen denen man im Alltag begegnet. Ergebnisse aus dem Feld des Graphenzeichnens stellen Schlüsselfaktoren dar, in Gebieten wie Web Computing, E-Commerce, VLSI, Schaltungsentwurf, Informationssysteme, Software Engineering, Algorithmische Kartographie, Bioinformatik, Netzwerktechnik und soziale Netzwerkanalyse.
- Sammlung von Literatur und Informationen für Lehrveranstaltungen zum Graphenzeichnen
Termine
| Di | Do | Thema | Folien | Literatur | |||
|---|---|---|---|---|---|---|---|
| 23.04. | Vorlesung | Einführung, kräftebasierte Layouts | v01.pdf | [KW01] Kap. 4 | |||
| 30.04. | Vorlesung | kräftebasierte Layouts: Varianten und Verbesserungen | v02.pdf | [KW01] Kap. 4 | |||
| 05.05. | Übung | 07.05. | Vorlesung | Flussmethoden: orthogonale planare Zeichnungen | v03.pdf | [BETT99] Kap. 5 | |
| 14.05. | Vorlesung | Knickminimierung in orthogonalen Zeichnungen | v04.pdf | [BETT99] Kap. 5 | |||
| 19.05. | Übung | 21.05. | Feiertag | ||||
| 28.05. | Vorlesung | Kompaktierung von orthogonalen Zeichnungen | v05.pdf | [BETT99] Kap. 5, [P01] | |||
| 02.06. | Übung | 04.06. | Vorlesung | Aufwärtsplanare Zeichnungen | v06.pdf | [BETT99] Kap. 6 | |
| 11.06. | Feiertag | ||||||
| 16.06. | Übung | 18.06. | Vorlesung | Aufwärtsplanare Zeichnungen, Winkelauflösung | v07.pdf | [BETT99] Kap. 6, [BV96] | |
| 25.06. | Vorlesung | Lagenlayouts | v08.pdf | [BETT99] Kap. 9, [KW01] Kap. 5 | |||
| 30.06. | Übung | 02.07. | Vorlesung | Teile und Herrsche: Zeichnen von Bäumen | v09.pdf | [BETT99] Kap. 3, [KW01] Kap. 3 | |
| 9.07. | Vorlesung | Bäume: Radiallayouts und konvexe Layouts | v10.pdf | [BETT99] Kap. 3, [CE07] | |||
| 14.07. | Übung | 16.07. | Vorlesung | Serienparallele Graphen | v11.pdf | [BETT99] Kap. 3, [BCDTT92], [HEL00] | |
| 23.07. | Vorlesung | Serienparallele Graphen, Planare Gitterzeichnungen | v12.pdf | [HEL00], [NR04] Kap. 4 |
Änderungen vorbehalten!
Literatur und Skripte
- Vorläufiges Vorlesungsskript (nur für Hörer der Vorlesung zugänglich)
- Kurzskripte zur Wiederholung wichtiger Begriffe: Skriptsammlung
| [BCDTT92] | P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, I. G. Tollis: How to draw a Series-Parallel Digraph, In: Proc. Scand. Workshop on Algorithm Theory 1992, LNCS Vol. 621 pp. 272-283, Springer-Verlag, 1992. |
| [BETT99] | G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999. |
| [CE07] | J. Carlson, D. Eppstein: Trees with Convex Faces and Optimal Angles In: Proc. Graph Drawing 2006, LNCS Vol. 4372 pp. 77-88, Springer-Verlag, 2007. |
| [HEL00] | S.-H. Hong, P. Eades, S.-H. Lee: Drawing series-prallel digraphs symetrically, In: Computational Geometry: Theory and Applications 17(3-4):165-188, Elsevier, 2000. |
| [KW01] | M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001 |
| [NR04] | T. Nishizeki, Md. S. Rahman: Planar Graph Drawing, Lecture Notes Series on Computing Vol. 12, World Scientific, 2004. |
| [P01] | M. Patrignani: On the complexity of orthogonal compaction In: Computational Geometry: Theory and Applications 19(1):47-67, Elsevier, 2001. |
| [BV96] | G. Di Battista, L. Vismara: Angles of Planar Triangular Graphs In: SIAM J. Discrete Math. 9(3):349-359, 1996. |