Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2013/2014
Algorithmen zur Visualisierung von Graphen

Algorithmen zur Visualisierung von Graphen

Wintersemester 2013/14

Allgemeines

  • Dozenten: Dr. Tamara Mchedlidze, PD Dr. Martin Nöllenburg
  • Vorlesung: Wöchentlich dienstags 9.45 - 11.15 in Raum SR301,
    (Informatikgebäude 50.34)
  • Übung: Voraussichtlich zwei-wöchentlich mittwochs 14.00 - 15.30 in SR 236,
    (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üfung: Die mündliche Prüfung besteht aus einem semesterbegleitenden Projekt (20%) und einer 20-minütigen Abschlussprüfung (80%)
  • Sprache: Teile der Vorlesung und Übung werden in englischer Sprache gehalten
  • Prüfungstermine: nächste Termine 9. April 2014, 15. Mai 2014, 10. Juni 2014

Aktuelles

  • Projektvorstellungen und interner Contest am 11.4.2014 ab 14:00 Uhr in Raum 301

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.

Termine

Änderungen vorbehalten.

Vorlesungen

Datum Thema Folien Literatur Dozent
Di, 22.10. 1. Vorlesung Einführung/Tree Layouts Einführung Skript Kap. 6 MN/TM
Di, 29.10. 2. Vorlesung Divide&Conquer: Tree Layouts Tree Layouts Skript Kap. 6.1, [LY07] TM
Di, 5.11. 3. Vorlesung Divide&Conquer: Series-Parallel Graphs SP-Graphs Skript Kap. 6.2, [HEL00] TM
Di, 12.11. 4. Vorlesung Incremental algorithms. Planar Straight-Line Layout: Shift Method Shift Method Shift method(book chapter) TM
Di, 19.11. 5. Vorlesung Incremental algorithms. Planar Straight-Line Layouts: Realizer method Realizer Method Realizer method(book chapter) TM
Di, 26.11. 6. Vorlesung Incremental algorithms. Orthogonal Layout. Biedl&Kant Skript Kap. 7 TM
Mi, 4.12. 7. Vorlesung Flussmethoden: orthogonale Zeichnungen VL7 Skript Kap. 4 MN
Di, 10.12. 8. Vorlesung Flussmethoden: orthogonale Zeichnungen Teil 2 VL8 Skript Kap. 4 MN
Di, 17.12. 9. Vorlesung Contact representations of planar graphs Rect_Dual [He93],[HK94](Section 4) TM
Weihnachtspause
Di, 7.1. 10. Vorlesung Kräftebasiertes Graphenzeichnen VL10 Skript Kap. 2 MN
Di, 14.1. 11. Vorlesung Lagenlayouts Teil 1 VL11 Skript Kap. 5, [ELS93] MN
Di, 21.1. 12. Vorlesung Lagenlayouts Teil 2 VL12 Skript Kap. 5, [EW94], [T13] Kap. 13 MN
Di, 28.1. 13. Vorlesung Zeichnen von Metro Maps VL13 [NW11] MN
Di, 4.2. 14. Vorlesung Pfadbreite und Fläche planarer Gitterzeichnungen VL14 lecture notes T. Biedl MN
Di, 11.2. 15. Vorlesung Wiederholung, Gastvorträge FlexDraw und Greedy Drawing MN

Übungen

Datum Thema Folien Literatur Dozent
Mi, 6.11. 1. Übung Trees and Series-Parallel Graphs TM
Mi, 20.11. 2. Übung Planar Straight-line Drawings TM
Di, 3.12. 3. Übung Schnyder realizer, st-ordering. TM
Mi, 11.12. 4. Übung Orthogonale Zeichnungen und Knickminimierung MN
Weihnachtspause
Mi, 8.1. 5. Übung Contact representations of planar graphs TM
Mi, 22.1. 6. Übung Kräftebasierte Zeichnungen und Lagenlayout ex6 MN
Mi, 5.2. 7. Übung Kreuzungsminimierung und Metro Maps ex7 MN

Gruppenprojekt: Orthogonal Grid Layout with Small Area

Termin Gruppe Datum Zeit Raum
1 Gruppe 1-4 Mi, 11.12. 13:00-14:00, 15:30-15:50 236
2 Gruppe 1 Mi, 15.1. 13:30
2 Gruppe 2 Mi, 15.1. 14:00
2 Gruppe 3 Mi, 15.1. 14:30
2 Gruppe 4 Mi, 15.1. 15:00

Literatur, Skripte, Zusatzmaterial

[BETT99] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
[T13] R. Tamassia: Handbook of Graph Drawing and Visualization, CRC Press, 2013.
[KW01] M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001
[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.
[He93] X. He On Finding the Rectangular Duals of Planar Triangular Graphs, SIAM J. Comput., Vol. 22(6), pages 1218–1226, 1993
[HEL00] S. Hong, P. Eades, S. Lee: Drawing Series Parallel Digraphs Symmetrically, Computational Geometry, Vol. 17, Issues 3–4, pages 165–188, 2000
[KH94] X. He, G. Kant Two algorithms for finding rectangular duals of planar graphs, LNCS, Springer, Vol. 790, pages 396-410, 1994
[LY07] C. Lin and H. Yen: On Balloon Drawings of Rooted Trees, Journal of Graph Algorithms and Applications, Vol. 11, no. 2, pages 431-452, 2007
[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.