Algorithmen zur Visualisierung von Graphen
Wintersemester 2014/15
Allgemeines
- Dozenten: Dr. Tamara Mchedlidze, PD Dr. Martin Nöllenburg
- Termine: montags 15:45 - 17:15 und mittwochs 15:45 - 17:15 in Raum SR301, (Informatikgebäude 50.34)
- 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: Teile der Vorlesung und Übung werden in englischer Sprache gehalten
- Prüfung: mündliche Prüfungstermine: 25.2., 25.3. 15.4., jeweils ab 16:15 Uhr; Anmeldung im Sekretariat; aktive Teilnahme an der Übung (inkl. Bearbeitung der Layoutaufgabe) ist Prüfungsvoraussetzung
Aktuelles
- Übung am 9.2. entfällt
- Layoutaufgabe bereit gestellt
- Prüfungstermine festgelegt (s.o.)
- Gastvortrag von Dr. Patrizio Angelini (Roma Tre University) am Mittwoch, 19.11
- Bitte für die Übung am Montag, 27.10. Laptops, Papier und Stifte mitbringen und yEd installieren
- Folien und Aufgabenblätter der ersten Vorlesung online
- erste Vorlesung am Mittwoch, 22.10.
- Vorlesungszeiten geändert (von Dienstag auf Montag wegen Terminkonflikt)
- Seite angelegt [19.09.2014]
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
| Datum | Thema | Folien | Literatur | Dozent | |
|---|---|---|---|---|---|
| Mi, 22.10. | 1. Vorlesung | Einführung | VL01 | - | MN |
| Mi, 29.10. | 2. Vorlesung | Divide&Conquer: Tree Layouts | VL2 | Skript Kap. 6 | TM |
| Mi, 5.11. | 3. Vorlesung | Divide&Conquer: Trees and Series-Parallel Graphs | VL3 | Skript Kap. 6.2, [LY07] | TM |
| Mi, 12.11. | 4. Vorlesung | Incremental algorithms. Planar Straight-Line Layout: Shift Method | Shift Method | Skript Kap.8, Shift method (book chapter) | TM |
| Mi, 19.11. | 5. Vorlesung | Guest-lecture: Data Structures for Planar Graph Embeddings | Planar Embeddings | s. letzte Folie | Patrizio Angelini |
| Mi, 26.11. | 6. Vorlesung | Incremental algorithms. Planar Straight-Line Layout: Realizer method | Realizer Method | Realizer method (book chapter) | TM |
| Mi, 3.12. | 7. Vorlesung | Contact representations of planar graphs | Contact Representations | [He93],[HK94](Section 4) | TM |
| Mi, 10.12. | 8. Vorlesung | Lagenlayouts Teil 1 | VL08 | Skript Kap. 5, [ELS93] | MN |
| Mi, 17.12. | 9. Vorlesung | Lagenlayouts Teil 2 | VL09 | Skript Kap. 5, [EW94], [T13] Kap. 13 | MN |
| Mo, 22.12. | 10. Vorlesung | Metro Maps | VL10 | [NW10] | MN |
| Mo, 12.1. | 11. Vorlesung | Flussmethoden: orthogonale Layouts Teil 1 | VL11 | Skript Kap. 4 | MN |
| Mi, 14.1. | 12. Vorlesung | Flussmethoden: orthogonale Layouts Teil 2, Aufwärtsplanarität | VL12 | Skript Kap. 4 | MN |
| Mo, 19.1. | 13. Vorlesung | Kräftebasiertes Graphenzeichnen | VL13 | Skript Kap. 2 | Ignaz Rutter |
| Mi, 4.2. | 14. Vorlesung | Incremental algorithms. Orthogonal layout. | VL14 | Skript Kap. 7 | TM |
| Mi, 11.2. | 15. Vorlesung | Rückblick, Gitterzeichnungen mit ILP | Tafel VL15 | [BBN+13] | MN |
Übungen
| Datum | Thema | Folien | Literatur | Dozent | |
|---|---|---|---|---|---|
| Mo, 27.10. | 1. Übung | Aesthetics | TM/MN | ||
| Mo, 10.11. | 2. Übung | Trees and SP-Graphs | TM | ||
| Mo, 8.12. | 3. Übung | Shift and Realizer Methods | TM | ||
| Mi, 7.1. | 4. Übung | Lagenlayouts | EX4 | MN | |
| Mi, 21.1. | 5. Übung | orthogonale Zeichnungen | Task 3 | MN/TM | |
| Mo, 9.2. | 6. Übung | Contact repr., st-ordering | TM |
Layout von Anwendungsgraphen
Ähnlich wie in der ersten Übung sollen bei dieser Aufgabe kreativ in Gruppen mit bis zu drei Personen unter Verwendung der in der Vorlesung erlernten Konzepte möglichst gute Layouts für drei Graphen aus den Anwendungsgebieten Schaltungslayout, biologische Netze und U-Bahn-Netze erstellt werden.
Abgabe: bis spätestens 29.1. 23:59 Uhr per Email an Tamara
Besprechung der Ergebnisse: in der Übung am 2.2. 15:45 Uhr
Beste Visualisierungen (Ergebnis der Abstimmung aller Übungsteilnehmer):
- Controller graph by Alexander Hantelmann and Henning Schulz,
- Biological network by Alexander Hantelmann and Henning Schulz,
- Metro map by Matthias Wolf and Michael Wegner.
Termine
Änderungen vorbehalten
| Mo | Mi | ||
|---|---|---|---|
| 20.10. | - | 22.10. | VL1 |
| 27.10. | UB1 | 29.10. | VL2 |
| 3.11. | - | 5.11. | VL3 |
| 10.11. | UB2 | 12.11. | VL4 |
| 17.11. | - | 19.11. | VL5 |
| 24.11. | - | 26.11. | VL6 |
| 1.12. | - | 3.12. | VL7 |
| 8.12. | UB3 | 10.12. | VL8 |
| 15.12. | - | 17.12. | VL9 |
| 22.12. | VL10 | 24.12. | - |
| Weihnachtspause | |||
| 5.1. | - | 7.1. | UB4 |
| 12.1. | VL11 | 14.1. | VL12 |
| 19.1. | VL13 | 21.1. | UB5 |
| 26.1. | - | 28.1. | - |
| 2.2. | UB6 | 4.2. | VL14 |
| 9.2. | | 11.2. | VL15 |
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 |
| [KH94] | 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 |
| [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. |