Seminar: Graphenzeichnen
Wintersemester 2007/2008
Allgemeines
- Termin: wöchentlich donnerstags 15:45 - 17:15 Uhr
- Ort: Seminarraum 301, Informatik-Hauptgebäude
Inhalt
Algorithmen, Theorie und Praxis zum Zeichnen von Graphen
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.
Dieses Seminar wird sich in erster Linie mit Forschungsergebnisse aus erster Hand befassen, welche auf der diesjährigen Graph Drawing Konferenz vorgestellt werden. Weiterhin stehen ausgewählte Themen des letzten Jahres zur Verfügung.
Ablauf
In der Vorbesprechung werden nach einer Einführung in das Gebiet des Graphenzeichnens eine Reihe von konkreten Themen vorgestellt und unter den Teilnehmern aufgeteilt. Nach etwa 2-3 Wochen der Einarbeitung stellen die Teilnehmer in Form eines Kurzvortrages von etwa 5 Minuten vor, welches Problem sie behandeln und was die Kernpunkte sind. Nach etwa weiteren 2-3 Wochen folgen anschließend an einem regelmäßigen wöchentlichen Termin die Langvorträge. Für die Vorträge ist inklusive Diskussion jeweils eine Doppelstunde vorgesehen. Ferner ist als schriftliche Ausarbeitung eine Seminararbeit zu erstellen. Diese Ausarbeitungen werden einheitlich in Latex geschrieben und anschließend in einen Seminarband zusammengestellt.
Terminübersicht
Dieser Kalender ist als iCal verfügbar.
Literatur
- Giuseppe di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing - Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
- Michael Kaufmann and Dorothea Wagner, editors. Drawing Graphs: Methods and Models. Vol. 2025 of LNCS, Springer Verlag, 2001.
Themenliste
Achtung: die Reihenfolge der Themen hat sich etwas geändert.
Straight-line Orthogonal Drawings of Binary and Ternary Trees
- Autor: Fabrizio Frati
- Konferenz: Graph Drawing 2007
- Vortragstermin: 29. November 2007
- Vortragender: Jakob Blomer
- Betreuer: Michael
- pdf beim Betreuer erhältlich
Edges and Switches, Tunnels and Bridges
- Autoren: David Eppstein, Marc van Kreveld, Elena Mumford und Bettina Speckmann
- Konferenz: WADS 2007
- Vortragstermin: 6. Dezember 2007
- Vortragender: Andreas Gemsa
- Betreuer: Martin
- Paper: arXiv – umfangreichere Fassung beim Betreuer erhältlich
Matched Drawings of Planar Graphs
- Autoren: Emilio Di Giacomo, Walter Didimo, Marc van Kreveld, Giuseppe Liotta und Bettina Speckmann
- Konferenz: Graph Drawing 2007
- Vortragstermin: 13. Dezember 2007
- Vortragender: Simon Wagner
- Betreuer: Martin
- pdf beim Betreuer erhältlich
Drawing with Fat Edges
- Autoren: Christian A. Duncan, Alon Efrat, Stephen G. Kobourov und Carola Wenk
- Konferenz: Graph Drawing 2001
- Vortragstermin: 13. Dezember 2007
- Vortragender: Frederik Zipp
- Betreuer: Michael
- Paper: Springer Verlag, Autorenseite
Moving Vertices to Make Drawings Plane
- Autoren: Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin und Alexander Wolff
- Konferenz: Graph Drawing 2007
- Vortragstermin: 20. Dezember 2007
- Vortragender: Daniel Karch
- Betreuer: Robert
- Paper: arXiv
Maximum Upward Planar Subgraphs of Embedded Planar Digraphs
- Autoren: Carla Binucci, Walter Didimo und Francesco Giordano
- Konferenz: Graph Drawing 2007
- Vortragstermin: 20. Dezember 2007
- Vortragender: Tsoncho Vasilev
- Betreuer: Martin
- pdf beim Betreuer erhältlich
Choosing Colors for Geometric Graphs Via Color Space Embeddings
- Autoren: David Eppstein, Michael Dillencourt und Michael Goodrich
- Konferenz: Graph Drawing 2006
- Vortragstermin: 10. Januar 2008
- Vortragender: Blaise Florian Tchana
- Betreuer: Robert
- Paper: Springer Verlag, arXiv
Efficient c-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
- Autoren: Giuseppe di Battista und Fabrizio Frati
- Konferenz: Graph Drawing 2007
- Vortragstermin: 10. Januar 2008
- Vortragender: Ze Li
- Betreuer: Robert
- pdf beim Betreuer erhältlich
IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs
- Autoren: Tim Dwyer, Yehuda Koren und Kim Marriott
- Journal: IEEE Transactions on Visualization and Computer Graphics
- Vortragstermin: 17. Januar 2008
- Vortragender: –
- Betreuer: Robert
- Paper: IEEE Xplore
- Zusatzmaterial: Stress Majorization
Drawings of Planar Graphs with Few Slopes and Segments
- Autoren: Vida Dujmovic, David Eppstein, Matthew Suderman und David R. Wood
- Journal: Computational Geometry: Theory and Applications
- Vortragstermin: 17. Januar 2008
- Vortragender: Robert Geisberger
- Betreuer: Martin
- Paper: Autorenseite
Dynamic Spectral Layout with an Application to Small Worlds
- Autoren: Ulrik Brandes, Daniel Fleischer und Thomas Puppe
- Konferenz: Graph Drawing 2005
- Vortragstermin: 24. Januar 2008
- Vortragender: Jens Doll
- Betreuer: Michael
- Paper: Autorenseite – umfangreichere Fassung beim Betreuer erhältlich
On Embedding a Graph on the Grid with the Maximum Number of Bends and Other Bad Features
- Autoren: Giuseppe di Battista, Fabrizio Frati und Maurizio Patrignani
- Konferenz: FUN 2007
- Vortragstermin: 24. Januar 2008
- Vortragender: Jérémie Thiery
- Betreuer: Michael
- Paper: Springer Verlag