Algorithmen zur Visualisierung von Graphen
Wintersemester 2011/12
Allgemeines
- Dozent: Dr. Marcus Krug, Dr. Ignaz Rutter
- Ü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.
- Sammlung von Literatur und Informationen für Lehrveranstaltungen zum Graphenzeichnen
Termine
| Datum | Thema | Folien | Literatur | |
|---|---|---|---|---|
| Mi, 19.10. | 1. Vorlesung | Einführung, kräftebasierte Layouts | vl01.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 | |
|---|---|---|
| 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
- Vorläufiges Vorlesungsskripts (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. |
| [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. |