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 2007/2008
Seminar: Graphenzeichnen

Seminar: Graphenzeichnen

Wintersemester 2007/2008

Allgemeines

Inhalt

Algorithmen, Theorie und Praxis zum Zeichnen von Graphen

Micro-Macro Kreislayout eines sozialen Netzwerkes
Analytische Visualisierung eines komplexen Netzwerkes

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.

Automatische Oktilineare Zeichnung des Londoner U-Bahn Planes

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

  1. Giuseppe di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing - Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
  2. 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