Algorithmen zur Visualisierung von Graphen
Wintersemester 2019/20
Allgemeines
- Dozenten: Dr. Tamara Mchedlidze, Torsten Ueckerdt
- Übungsleiter: Dr. Marcel Radermacher
- Termine: Dienstag in SR236 und Mittwoch in SR301 jeweils von 14:00 Uhr bis 15:30 Uhr
- Skript: Die Vorlesung orientiert sich an der dem Skript (nur für Hörer zugänglich), zusätzlich gibt es ergänzendes Material
- Credits: Es werden für diese Vorlesung 5 Leistungspunkte vergeben
- Module: Die Vorlesung kann in dem Modul T-INFO-104390 geprüft werden
- Sprache: Vorlesung: Englisch, Übung: Deutsch
Aktuelles
21.01.2020 Die Prüfungen finden am 09., 10. und 11.03.2020 (keine freien Plätze mehr am 11.03.) statt. Zur Anmeldung senden Sie bitte eine E-Mail an: sekr [dash] wagner [at] ira [dot] uka [dot] de.
16.10.2019 First excercise is online.
25.9.2019 The web-page set up.
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
Vorlesungen & Übungen
Vorlesungen und Übungen werden voraussichtlich an den folgenden Terminen stattfinden (Änderungen vorbehalten).
| Datum | Thema | Folien | Literatur | |
|---|---|---|---|---|
| Di, 15.10. | 1. Vorlesung | Introduction | ||
| Mi, 16.10. | 2. Vorlesung | Layout problem. Tree layouts. | [BETT99] Chapter 3.1.2, Skript: Chapter 6.1 | |
| Di, 22.10. | 1. Übung | |||
| Mi, 23.10. | 3. Vorlesung | Tree layouts. Series-Paralles Graphs. | Trees S-P | Trees: [BETT99] Chapters 3.1.3-4, Skript: page 86, Chapter 6.1.2. Additional [SR83] S-P: [BETT99] Chapter 3.2, 11.1, Skript: Chapter 6. Additional [HEL00], [EH13] |
| Mi, 30.10. | 4. Vorlesung | Symmetry in Series-Parallel Graphs. Planar Straight-line drawings. Shift Method. | [NR04] Chapter 4.2. | |
| Mi, 6.11. | 5. Vorlesung | Planar Straight-line drawings. Realizer Method. | [NR04] Chapter 4.3 | |
| | | |||
| Mi, 13.11. | 6. Vorlesung | Orthogonal Layouts (Incremental) | Skript Kap. 7 | |
| Di, 19.11. | 2. Übung | |||
| Mi, 20.11. | 7. Vorlesung | Flow Methods: Orthogonal Layouts (Flow) – Part I | ||
| Mi, 27.11. | 3. Übung | |||
| Mi, 4.12. | 8. Vorlesung | Flow Methods: Orthogonal Layouts (Flow) – Part II | ||
| Mi, 11.12. | 9. Vorlesung | Flow Methods: Upward Planarity | ||
| Mi, 18.12. | 4. Übung | |||
| Mi, 8.1. | 10. Vorlesung | Layered Layouts | ||
| Mi, 15.1. | 5. Übung | |||
| Mi, 22.1. | 11. Vorlesung | Layered Layouts II | ||
| Mi, 29.1. | 12. Vorlesung | Force-Directed Algorithms | pdf pdf | |
| Mi, 5.2. | 6. Übung |
Übungsblätter
| Blatt | Hinweis | Ausgabe | Diskussion |
|---|---|---|---|
| 1. Übungsblatt | 17.10 | 22.10 | |
| 2. Übungsblatt | 6.11 | 12.11 | |
| 3. Übungsblatt | 20.11 | 27.11 | |
| 4. Übungsblatt | 04.12 | 18.12 | |
| 5. Übungsblatt | 18.12 | 15.01 | |
| 6. Übungsblatt | 20.01 | 05.02 |
Literatur, Skripte, Zusatzmaterial
- Graphs to draw (Graph to be drawn by hand or using yEd after the first lecture)
- Vorläufiges Vorlesungsskripts (nur für Hörer der Vorlesung zugänglich)
- Kurzskripte zur Wiederholung wichtiger Begriffe: Skriptsammlung
- Spring-Embedder Java-Applet
- Animation zur Verzerrung der London Tube Map
- PIGRA Tool zum Modellieren und Erstellen gitterbasierter Graphenlayouts
- Barnes-Hut Online Implementation of Barnes-Hut approximation
| [BBN+13] | T. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin, I. Rutter: Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings, In: Graph Drawing, LNCS 8242, pp.460-471, Springer 2013. |
| [BETT99] | G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999. |
| [ELS93] | P. Eades, X. Lin, W. F. Smyth: A fast and effective heuristic for the feedback arc set problem, Information Processing Letters, 47(6):319–323, 1993 |
| [EW94] | Eades, P., Wormald, N. C.: Edge crossings in drawings of bipartite graphs. Algorithmica, 1994, 11(4):379–403. |
| [KW01] | M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001 |
| [HK94] | X. He, G. Kant Two algorithms for finding rectangular duals of planar graphs, LNCS, Springer, Vol. 790, pages 396-410, 1994 |
| [He93] | X. He On Finding the Rectangular Duals of Planar Triangular Graphs, SIAM J. Comput., Vol. 22(6), pages 1218–1226, 1993 |
| [EH13] | P. Eades, S. Hong Symmetric Graph Drawing Handbook of Graph Drawing and Visualization 2013: 87-113 |
| [HEL00] | S. Hong, P. Eades, S. Lee: Drawing Series-Parallel Digraphs Symmetrically, Computational Geometry, Vol. 17, Issues 3–4, pages 165–188, 2000 |
| [LY07] | C. Lin, H. Yen: On Balloon Drawings of Rooted Trees, JGAA, vol.11, no.2, pp.431-452 |
| [NR04] | T. Nishizeki, Md. S. Rahman: Planar Graph Drawing, 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. |
| [T13] | R. Tamassia: Handbook of Graph Drawing and Visualization, CRC Press, 2013. |
| [SR83] | K. J. Supowit, E. M. Reingold The complexity of drawing trees nicely Acta Informatica, Volume 18, Issue 4, pp 377–392 |