Institut für Theoretische Informatik, Algorithmik

Algorithmen zur Visualisierung von Graphen

Sommersemester 2009

Allgemeines

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

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

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

Übungsblätter

Übungsblatt Ausgabe Besprechung
Blatt 1 27.04. 05.05.
Blatt 2 11.05. 19.05.
Blatt 3 25.05. 02.06.
Blatt 4 08.06. 16.06.
Blatt 5 19.06. 30.06.
Blatt 6 07.07. 14.07.