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 2012/2013
Algorithmen zur Visualisierung von Graphen

Algorithmen zur Visualisierung von Graphen

Wintersemester 2012/13

Allgemeines

  • Dozenten: Dr. Tamara Mchedlidze, PD Dr. Martin Nöllenburg, Dr. Ignaz Rutter
  • 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üfungstermine: erster Termin: 6. März 2013 ab 9:00 Uhr, zweiter Termin: 24. April 2013 ab 9:00 Uhr. Anmeldung im Sekretariat bei Frau Beckert. Für Diplomprüfungen muss ein individueller Termin vereinbart werden.

Aktuelles

  • nächste Prüfungstermine: 6.3. und 24.4.

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

Datum Thema Folien Literatur Dozent
Di, 16.10. 1. Vorlesung Einführung Einführung IR
Di, 23.10. 2. Vorlesung Rekursive Algorithmen und Baumzeichnungen Rekursive Zeichenalgorithmen IR
Di, 30.10. 3. Vorlesung Rekursive Algorithmen, serien-parallele Graphen siehe 2. Vorlesung IR
Mi, 31.10. 1. Übung Rekursive Algorithmen Folien zur 1. Übung IR
Di, 6.11. 4. Vorlesung Flußmethoden, Knickminimierung in orthogonalen Zeichnungen Flußmethoden IR
Di, 13.11. 5. Vorlesung Flußmethoden, Knickmimierung in orthogonalen Zeichnungen, Aufwärtsplanarität Flußmethoden II IR
Di, 20.11. 6. Vorlesung Incremental algorithms. Planar straight-line layouts: Shift method Shift method TM
Mi, 21.11. 2. Übung Orthogonale Layouts, Aufwärtsplanarität Übung zu Flußmethoden IR
Di, 27.11. 7. Vorlesung Incremental algorithms. Planar straight-line layouts: Realizer method Realizer method Realizer method(book chapter) TM
Mi, 28.11. 3. Übung st-graphs, Canonical Ordering, Barycentric representation TM
Di, 4.12. 8. Vorlesung Incremental algorithms. Orthogonal layout. Biedl&Kant TM
Di, 5.12. 4. Übung Schnyder realizer, st-ordering TM
Di, 11.12. 9. Vorlesung Lagenlayouts: Kreise brechen, Lagenzuordnung LagenlayoutsSkript, [T13] Kap. 13, [BETT99] Kap. 9 MN
Di, 18.12. 10. Vorlesung Lagenlayouts: Kreuzungsminimierung, Knotenpositionierung Lagenlayouts2Skript, [T13] Kap. 13, [BETT99] Kap. 9, [EW94] MN
Mi, 19.12. 5. Übung Lagenlayouts Folien 5. Übung MN
Di, 8.1. 11. Vorlesung Kräftebasierte Layouts KräftebasiertSkript, [BETT99] Kap. 10, [T13] Kap. 12, [KW01] Kap. 4 MN
Di, 15.1. 12. Vorlesung Metro Map Layout MetroMaps [NW11] MN
Mi, 16.1. 6. Übung Kräftebasierte Layouts Folien 6. Übung Schwerpunktlayouts: Skript, Kap. 3 MN
Di, 22.1. 13. Vorlesung Contact representations of planar graphs Contact Representations REL (look Section 4) Rect Dual (look Sections 2-4) TM
Di, 29.1. 14. Vorlesung Pathwidth and planar graph drawing pathwidth notes Therese Biedl
Mi, 30.1. 7. Übung metro maps, contact representations TM, MN
Di, 5.2. 15. Vorlesung Rückblick, Lombardi-Baumzeichnungen, Flex-Draw Rückblick/Ausblick,Lombardi,FlexDraw IR, MN

Übungsblätter

Ausgabe Thema PDF
23.10. Bäume und Serien-Parallele Graphen 1. Übungsblatt
6.11. Orthogonale Zeichnungen 2. Übungsblatt
20.11. st-graphs, Canonical Ordering, Barycentric representation 3. Übungsblatt
27.11. Schnyder realizer, st-ordering 4. Übungsblatt
13.12. Lagenlayouts 5. Übungsblatt
12.01. Kräftebasierte Layouts 6. Übungsblatt
25.01. Metro Maps, Contact Representations 7. Übungsblatt

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