Algorithmen zur Visualisierung von Graphen
Wintersemester 2017/18
Allgemeines
- Dozenten: Dr. Tamara Mchedlidze
- Übungsleiter: Dr. Marcel Radermacher
- Termine: Mittwoch und Donnerstag jeweils von 14:00 Uhr bis 15:30 Uhr in Raum SR301
- Skript: Die Vorlesung orientiert sich eng an der aktualisierten Version des Vorlesungsskripts (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 den Modulen IN4INDAA, IN4INALGVG, IN4INAEA und IN4INNWA geprüft werden
- Sprache: Vorlesung: Englisch, Übung: Deutsch
Prüfung
Prüfungstermine sind der 21.02.2017 und 14.03.2018. Anmeldung bitte rechtzeitig (mindestens eine Woche vor der Prüfung) per Mail im Sekretariat (sekr [dash] wagner [at] ira [dot] uka [dot] de). Voraussetzung für das erfolgreiche Bestehen der Prüfung ist das Vorrechnung einer Übung und das Bearbeiten der 'Practical Task'.
Aktuelles
- 24.01.2017 The lecture on 1st of February on Contact Representations will take place in ZKM at the OpenHub space of the Open Codes Exhibition. The topic of the lecture is related to the visualisation concept behind one of the works in the exhibition "OpMap: What should one eat?".
- 21.12.2017 Die Vorlesung muss heute leider ausfallen.
- 07.12.2017 Die nächste Übung wurde auf den 20.12 verschoben.
- 07.12.2017 Die Vorlesung findet nicht statt.
- 30.11.2017 Die Vorlesung wird heute stattfinden.
- 08.11.2017 Die zweite Übung findet nicht am
15.11.2017sondern am 23.11.2017 statt. Die Vorlesung findet in dieser Woche am 22.11.2017 statt. - 20.10.2017: The mailing list have been created. If you have given us your email but have not got a subscription notification, or have not attended the first lecture but want to subscribe to the list, please send an email to Marcel.
- 18.10.2017: Die erste Vorlesung findet am 19.10 um 14:00 Uhr in Raum SR301 statt. Bitte bringt eure Notebooks mit, wir werden in die Vorlesung mit einer praktischen Einheit zum Zeichnen von Graphen einsteigen.
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 | |
---|---|---|---|---|
Do, 19.10. | 1. Vorlesung | Introduction | slides | Skript: Chapter 1, [BETT99] Chapter 2.1 |
Do, 26.10. | 2. Vorlesung | Drawing conventions and aesthetics. Level-based layout for trees. | slides | [BETT99] Chapter 3.1.2, Skript: Chapter 6.1 |
Do, 02.11. | 3. Vorlesung | HV-layout, Radial layout for trees. | slides | [BETT99] Chapters 3.1.3-4, Skript: page 86, Chapter 6.1.2. Additional [SR83] |
Mi, 08.11. | 1. Übung | Trees | - | - |
Do, 09.11. | 4. Vorlesung | Series-parallel graphs | slides | [BETT99] Chapter 3.2, 11.1, Skript: Chapter 6. Additional [HEL00], [EH13] |
Do, 16.11. | 5. Vorlesung | Planar Straight-line drawings. Shift Method. | slides | [NR04] Chapter 4.2. |
Mi, 22.11. | 6. Vorlesung | Planar Straight-line drawings. Realizer Method. | slides | [NR04] Chapter 4.3. |
Do, 23.11. | 2. Übung | Canonical Ordering, Barycentric Coordinates. | - | - |
Mi, 29.11. | 3. Übung | Canonical Ordering, Realizer. | - | - |
Do, 30.11. | 7. Vorlesung | Force Directed Layouts. | slides | Skript Kap. 2 |
Do, 07.12. | Vorlesung | Cancelled | - | - |
Mi, 13.12. | 8. Vorlesung | Layered Layout 1. | slides | Skript: Chapter 5. |
Mi, 20.12. | 4. Übung | Force Directed, Layered Layout | - | - |
Do, 21.12. | Vorlesung | Fällt aus! | - | - |
Mi, 10.01. | Übung verschoben | - | - | - |
Do, 11.01. | 9. Vorlesung | Layered Layout 2. | slides | Skript: Chapter 5. [BETT99] Chapter 9. |
Mi, 17.01. | 5. Übung | Layered Layouts | - | |
Do, 18.01. | 10. Vorlesung | Orthogonal Layout. Flow Method. | slides | Skript: Chapter 4. [BETT99] Chapter 5. |
Mi, 24.01. | 6. Übung | Orthogonal Layout | - | - |
Do, 25.01. | 11. Vorlesung | Upward Planar Drawings. | slides | Skript: Chapter 4.3.1-4.3.2. [BETT99] Chapter 6. |
Do, 01.02. | 12. Vorlesung | Contact Representations. | slides | [He93],[HK94](Section 4) |
Mi, 07.02. | 7. Übung | Extended Canonical Ordering, Contact Representation | - | - |
Do, 08.02. | 13. Vorlesung | Wrap-up and overview. | - |
Übungsblätter
Practical Task: Zeichnet in 2-3 Gruppen einen der beiden Graphen der diesjährigen Graph Drawing Challenge. Ihr dürft dafür zur Unterstützung Software bzw. Libraries nutzen. Schickt die Zeichnung bis zum 28.02.2018 an Tamara und Marcel. Die Zeichnung ist Voraussetzung um erfolgreichen Bestehen der Prüfung.
Blatt | Ausgabe | Diskussion |
---|---|---|
1. Übungsblatt | 03.10 | 08.11 |
2. Übungsblatt | 16.11 | 23.11 |
3. Übungsblatt | 22.11 | 29.11 |
4. Übungsblatt | 12.12 | 20.12 |
5. Übungsblatt | 04.01 | 17.01 |
6. Übungsblatt | 18.01 | 24.01 |
7. Übungsblatt | 02.02 | 07.02 |
Literatur, Skripte, Zusatzmaterial
- Graphenzeichnen von Hand (Aufgabenblätter aus der ersten Vorlesung)
- 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 (aus VL15)
[BBN+13] | T. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin, I. Rutter: Using ILP/SAT to determin 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 |