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 2016/2017
Algorithmen zur Visualisierung von Graphen

Algorithmen zur Visualisierung von Graphen

Wintersemester 2016/17

Allgemeines

  • Dozenten: Dr. Tamara Mchedlidze, Dr. Benjamin Niedermann
  • Termine: montags 9:45 - 11:15 in Raum SR301 und mittwochs 9:45 - 11:15 in Raum SR -119, (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: Vorlesung: Englisch, Übung: Deutsch

Aktuelles

25. Oktober: Bitte für die erste Übung nach Möglichkeit einen Laptop mitbringen. Es ist eine Gruppenarbeit geplant, für die Laptops benötigt werden. Außerdem wird das Tool yEd benötigt: http://www.yworks.com/products/yed

5. December: The lecture on 12th of December will not take place.

5. December: The slides for the Layered Layout for 5th of December are updated with new proofs.

29. December: The data set in xml format on publications in the Proceedings of Graph Drawing conference is now available. Please submit your visualizations by Monday 30th of January.

16. January

Lecture on 18.01 is cancelled. Lecture on 01.02 is introduced.

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

Vorlesungen werden voraussichtlich an den folgenden Terminen stattfinden (Änderungen vorbehalten).

Datum Thema Folien Literatur
Mo, 17.10. 1. Vorlesung Einführung pdf Book of Di Batista et al. Sections 2.1 and 2.2
Mo, 24.10. 2. Vorlesung Tree Layouts pdf Skript Kap. 6.1
Mo, 31.10. 3. Vorlesung Series-Parallel Graphs pdf Skript Kap. 6.2, [HEL00]
Mo, 07.11. 4. Vorlesung Layouts for planar graphs: Shift method pdf Skript Kap.8, Shift method (book chapter)
Mo, 14.11. 5. Vorlesung Layouts for planar graphs: Realizer method pdf Realizer method (book chapter)
Mo, 21.11. 6. Vorlesung Force-directed layout pdf Skript Kap. 2
Mo, 28.11. -  
Mo, 05.12. 7. Vorlesung Layered drawings 1 pdf Skript Kap 5., [ELS93]
Mo, 12.12. -  
Mo, 19.12. 8. Vorlesung Layered drawings 2 pdf Skript Kap 5., Sections 9.2.1, 9.2.3-4 in [BETT99]
Weihnachtsferien
Mo, 9.1. 9. Vorlesung Incremental algorithms. Orthogonal drawing. pdf Skript Kap. 7
Mo, 16.01. 10. Vorlesung Flow and orthogonal drawings pdf Skript Kap 4.1-4.2
Mo, 23.01. 11. Vorlesung Flow and upward planarity pdf Skript Kap. 4.3
Mo, 30.01. 12. Vorlesung Contact representations pdf updated 31/1/17 [He93],[HK94](Section 4)
Mi, 01.02. 13. Vorlesung Contact representations
Mo, 06.02. 14. Vorlesung Overview and conclusions pfd Black board

/

Übungsblätter

Blatt Ausgabe Diskussion
1. Übungsblatt 26.10 09.11
2. Übungsblatt 14.11 23.11
3. Übungsblatt 30.11 14.12
4. Übungsblatt 16.12 11.01
5. Übungsblatt 18.01 25.01
6. Übungsblatt 30.01 08.02

Übungen

Übungen werden voraussichtlich an den folgenden Terminen stattfinden (Änderungen vorbehalten).

Datum Thema Folien
Mi, 26.10. 1. Übung Einführung Übung 1
Mi, 09.11. 2. Übung
Mi, 23.11. 3. Übung
Mi, 14.12. 4. Übung
Mi, 11.01. 5. Übung Übung 5
Mi, 25.01. 6. Übung
Mi, 08.02. 7. Übung Übung 7

Graphen für erste Übung.

Übersicht über Termine

Änderungen vorbehalten

Mo Mi
17.10. VL01 19.10. -
24.10. VL02 26.10. ÜB1
31.10. VL03 02.11. -
07.11. VL04 09.11. ÜB2
14.11. VL05 16.11. -
21.11. VL06 23.11. ÜB3
28.11. - 30.12. -
05.12. VL07 07.12. -
12.12. - 14.12. ÜB4
19.12. VL08 21.12. -
Weihnachtspause
09.01. VL9 11.01. ÜB5
16.01. VL10 18.01. -
23.01. VL11 25.01. ÜB6
30.01. VL12 01.02. VL13
06.02. VL14 08.02. ÜB7

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