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 2010/2011
Algorithmen zur Visualisierung von Graphen

Algorithmen zur Visualisierung von Graphen

Wintersemester 2010/11

Allgemeines

  • Dozent: Dr. rer. nat. Robert Görke
  • Vorlesung: Wöchentlich mittwochs 14.00 - 15.30 in SR 236 (Informatikgebäude 50.34),
    erstmalig am 20. Oktober
  • Übung: Es findet keine separate Übung statt, Übungsmaterial wird es jedoch geben
  • 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

Aktuelles

  • [13.01.] Die Folien zum Lagenlayout sind noch überarbeitet worden
  • [29.11.] Material zu HV-trees is verlinkt (siehe Tabellenzeile von P. Eades)
  • [29.11.] Drittes Übungsblatt ist online (siehe unten)
  • [20.11.] Etwas verspätet: 2. Übungsblatt ist online (siehe unten)
  • [20.11.] Beispiel zum Matrix-Gerüst-Satz steht bereit (siehe unten)
  • [10.11.] Fund: nach Peter Eades' Vortrag lag ein einsamer USB-Stick in SR236
  • [04.11.] Vergesst die letzte Meldung, Vorlesung am 17.11. wie gewohnt in SR236
  • [03.11.] Vorlesung am 17.11. ist im AVG (Geb. 50.41) in Raum 045/046
  • [03.11.] Die Tutte-Folie ist wieder aufgetaucht (siehe Slides)
  • [28.10.] Peter Eades wird am 10.11. in der Vorlesung (normaler Ort) vortragen
  • [21.10.] Vorlesung am 27.10. ausnahmsweise in SR-118
  • [21.10.] Folien von Vorlesung 1 und 1. Übungsblatt online
  • [08.09.] diese Seite wurde erstellt

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

Mi Thema Folien Literatur
20.10. Vorlesung Einführung, kräftebasierte Layouts v01.pdf [KW01] Kap. 4
27.10. Vorlesung kräftebasierte Layouts: Varianten und Verbesserungen v02.pdf [KW01] Kap. 4
03.11. Vorlesung Vergröberungen, globale Optimierung, Schwerpunktlayouts, Spektrale Layouts v03.pdf siehe Skript
10.11. Vorlesung Featuring Vortrag von Peter Eades hv-trees.zip Skript Kap. 6
17.11. Vorlesung Knickminimierung für orthogonale Zeichnungen v05.pdf [BCDTT92] Skript Kap. 4
24.11. Vorlesung Kompaktierung und NP-Schwere v06.pdf [BCDTT92] Skript Kap. 4
01.12. Vorlesung Zusammenfassung Orthogonales, Übungsblatt, Start Aufwärtsplanares v07.pdf siehe Skript
08.12. Vorlesung Aufwärtsplanare Layouts v08.pdf siehe Skript
15.12. Termin fällt aus
22.12. Vorlesung Winkelauflösung, Lagenlayouts v09.pdf, layerlayout.pdf Skript Kap. 5, [BETT99] 9
29.12. Termin fällt aus
05.01. Termin fällt aus
12.01. Vorlesung Lagenlayouts, Evaluation layerlayout.pdf Skript Kap. 5, [BETT99] 9
19.01. Vorlesung Teile und Herrsche: Baumlayouts v11.pdf Skript Kap. 6, [BETT99] 3
26.01. Vorlesung Konvexe Baumlayouts und serienparallele Graphen v12.pdf Skript Kap. 6, [BETT99] 3
02.02. Vorlesung Serienparallele Graphen (siehe naechste VL.) Skript Kap. 6, [BETT99] 3
09.02. Vorlesung Symmetrien in SP-Graphen, Planare Gitterzeichnungen v14.pdf Skript Kap. 6+8

Übungsblätter

Ausgabe Thema PDF
20.10. Potential zu Kräften, Verhalten von Spring-Embedder ueb01.pdf
20.11. Beispiel zum Matrix-Gerüst-Satz matrixgeruest.pdf
20.11. Matrix-Gerüst, Eigenwerte und Planarität ueb02.pdf
24.11. Knicke und Gitterueb03.pdf
22.12. Aufwärtsplanaritätueb04.pdf
26.01. Sichtbarkeit und Kreuzungen ueb05.pdf
08.02. ueb06.pdf

Literatur und Skripte

[BCDTT92] P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, I. G. Tollis: How to draw a Series-Parallel Digraph, In: Proc. Scand. Workshop on Algorithm Theory 1992, LNCS Vol. 621 pp. 272-283, Springer-Verlag, 1992.
[BETT99] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
[CE07] J. Carlson, D. Eppstein: Trees with Convex Faces and Optimal Angles In: Proc. Graph Drawing 2006, LNCS Vol. 4372 pp. 77-88, Springer-Verlag, 2007.
[HEL00] S.-H. Hong, P. Eades, S.-H. Lee: Drawing series-prallel digraphs symetrically, In: Computational Geometry: Theory and Applications 17(3-4):165-188, Elsevier, 2000.
[KW01] M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001
[NR04] T. Nishizeki, Md. S. Rahman: Planar Graph Drawing, Lecture Notes Series on Computing Vol. 12, World Scientific, 2004.
[P01] M. Patrignani: On the complexity of orthogonal compaction In: Computational Geometry: Theory and Applications 19(1):47-67, Elsevier, 2001.
[BV96] G. Di Battista, L. Vismara: Angles of Planar Triangular Graphs In: SIAM J. Discrete Math. 9(3):349-359, 1996.