Institut für Theoretische Informatik, Algorithmik

Algorithmen zur Visualisierung von Graphen

Wintersemester 2011/12

Allgemeines

  • Übungsleiter: Dr. Thomas Bläsius
  • Vorlesung: Wöchentlich mittwochs 14.00 - 15.30 in Raum -108,
    (Informatikgebäude 50.34)
  • Übung: Voraussichtlich zwei-wöchentlich donnerstags 14.00 - 15.30 in SR 301,
    (Informatikgebäude 50.34)
  • Skript: Die Vorlesung orientiert sich eng an der aktualisierte Version des Vorlesungsskripts (nur für Hörer zugänglich), zusätzlich gibt es gegebenenfalls ergänzendes Material
  • Credits: Es werden für diese Vorlesung 5 Credits vergeben
  • Prüfungstermine: Donnerstag 01.03.2012 ab 9:00 Uhr und Freitag 30.03.2012 ab 9:00 Uhr. Bitte meldet Euch bis spätestens 10 Tage vor dem gewünschten Termin bei Frau Beckert in Raum 321 an.
  • Zusätzlicher Prüfungstermin: Donnerstag, 19. April ab 9:00. Bitte meldet Euch bis spätestens 10 Tage vor dem gewünschten Termin bei Frau Beckert in Raum 321 an.

Aktuelles

  • [26.01.] Achtung: Die sechste und letzte Übung findet schon am 2.2.2012 Statt.
  • [26.01.] Sechstes Übungsblatt ist online
  • [13.01.] Fünftes Übungsblatt ist online
  • [13.12.] Virtes Übungsblatt ist jetzt auch online verfügbar
  • [23.11.] In der Woche vor Weihnachten werden Übung und Vorlesung vertauscht. Am 21.12. ist Übung, am 22.12. Vorlesung.
  • [17.11.] Drittes Übungsblatt ist online
  • [03.11.] Zweites Übungsblatt ist online
  • [26.10.] Fehler in Übungsblatt 1 korrigiert (Aufgabe 5)
  • [20.10.] Erstes Übungsblatt ist online
  • [20.10.] Heute findet in Raum 301 statt der Übung eine Vorlesung statt

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

Datum Thema Folien Literatur
Mi, 19.10. 1. Vorlesung Einführung, kräftebasierte Layoutsvl01.pdf[KW01] Kap. 4
Do, 20.10. 2. Vorlesung kräftebasierte Layouts: Varianten, Beschleunigungstechniken vl02.pdf[KW01] Kap. 4, [GK01]
Mi, 26.10. 3. Vorlesung Globale und Lokale Optimierung vl03.pdf [KW01] Kap. 4
Mi, 02.11. 4. Vorlesung Knickminimierung bei orthogonalen Layouts vl04.pdf
Do, 03.11. 1. Übung
Mi, 09.11. 5. Vorlesung Knickmimierung und Aufwärtsplanarität vl05.pdf
Mi, 16.11. 6. Vorlesung Winkelauflösung und SPQR-Bäume vl06.pdf
Do, 17.11. 2. Übung Aufwärtsplanarität und orthogonale Layouts ueb02.pdf
Mi, 23.11. 7. Vorlesung Lagenlayouts Teil I vl07.pdf [KW01] Kap. 5, [ELS93]
Mi, 30.11. 8. Vorlesung Lagenlayouts Teil II vl08.pdf [KW01] Kap. 5, [EW94],[GKNV93],[GMW01]
Do, 01.12. 3. Übung
Mi, 07.12. 9. Vorlesung Metro Maps vl09.pdf [NW11]
keine Veranstaltung am 14./15.12.
Mi, 21.12. 4. Übung Lagenlayouts und Metro Maps ueb04.pdf
Do, 22.12. 10. Vorlesung Baumlayouts Folien, siehe nächste Vorlesung; Vortrag von Peter Eades
Mi, 11.1. 11. Vorlesung Bäume und serien-parallele Graphen vl10.pdf
Mi, 18.1. 12. Vorlesung Symmetrien und inkrementelle Methoden v12.pdf
Mi, 25.1. 13. Vorlesung Gitterzeichnungen vl13.pdf
Do, 26.1. 5. Übung Teile-und-Herrsche und s-t-Ordnungen ueb05.pdf
Mi, 1.2. 14. Vorlesung Kontakt- und Schnittrepräsentationen v14.pdf
Do, 2.2. 6. Übung Inkrementelle Methoden ueb06.pdf
Mi, 8.2. 15. Vorlesung

Übungsblätter

Ausgabe Thema PDF
20.10. Kräfte-basierte Verfahren & globale/lokale Optimierung ueb01.pdf
20.10. Beispiel zum Matrix-Gerüst-Satz handout_matrixgeruest.pdf
03.11. Orthogonale Layouts ueb02.pdf
17.11. st-Graphen, SPQR-Bäume und Lagenlayouts ueb03.pdf
01.12. Lagenlayouts und Metro Maps ueb04.pdf
13.01. Teile-und-Herrsche und s-t-Ordnungen ueb05.pdf
26.01. Inkrementelle Methoden ueb06.pdf

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.
[ELS93] Eades, P., Lin, X., and Smyth, W. F: A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 1993, 47:319–323.
[EW94] Eades, P., Wormald, N. C.: Edge crossings in drawings of bipartite graphs. Algorithmica, 1994, 11(4):379–403.
[GK01] P. Gajer and S.G. Kobourov: GRIP: Graph dRawing with Intelligent Placement , Springer-Verlag, 2001
[GKNV93] Gansner, E. R., Koutsofios, E., North, S. C., Vo, K.-P.: A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 1993, 19(3):214–230.
[GMW01] C. Gutwenter, P. Mutzel, R. Weiskircher: Inserting an edge into a planar graph., Proc. 12th Ann. ACM-SIAM Symp. Discrete Algorithms, 2001
[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.
[NW11] M. Nöllenburg, A. Wolff: Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming, In: IEEE Transactions on Visualization and Computer Graphics 17(5):626-641, 2011.
[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.