Institut für Theoretische Informatik, Algorithmik

Algorithmen zur Visualisierung von Graphen

Wintersemester 2014/15

Allgemeines

  • 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.

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):

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. UB7 11.2. VL15

Literatur, Skripte, Zusatzmaterial

[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.