Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
Über den Lehrstuhl
  Arbeitsgebiete
  Mitarbeiter
  Kontakt
Lehre
  Lehrveranstaltungen
  Lehrstuhlbibliothek
  Infos für Studierende
Forschung
SEA 2009
Seminar: Automatisches Zeichnen von Graphen

Seminar: Automatisches Zeichnen von Graphen

Wintersemester 2004/05

Prof. Dr. Petra Mutzel,
Dipl.-Inform. Carsten Gutwenger, Dipl.-Inform. Karsten Klein, Dipl.-Ing. Markus Chimani

Vorträge: Di 18.01.2005 - 08.02.2005 14.00 - 18.30 Uhr / JvF20, Raum 2.54


Diese Veranstaltung ist ein Seminar für Studierende im Hauptstudium.

Termine

Das Seminar wird, soweit nicht anders angegeben, dienstags vom 18. Januar bis zum 8. Februar 2005 in JvF 20 / Raum 2.54 von 14:00 Uhr bis 18:30 Uhr stattfinden.

Termin Vortragende(r) Thema BetreuerIn
18.01.2005 Jens Schmidt M. van Kreveld, T. Strijk, A. Wolf:
Point Labeling with Sliding Labels
Comp. Geometry: Theory and Applications 13, pages 21-47, 1999 		Karsten Klein
  Rüdiger Ehlers D. Ebner, G. Klau, R. Weiskircher:
Label Number Maximization in the Slider Model
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Karsten Klein
25.01.2005
GB4, R113 		Iris Paternoster P. Healy, K. Lynch:
Fixed-Parameter Tractable Algorithms for Testing Upward Planarity
Proc. of 31st Annual Conference on Current Trends in Theory and Practice of Informatics (SofSem), 2005, to appear 		Petra Mutzel
  Monika Enns M. Suderman, S. Whitesides:
Experiments with the Fixed-Parameter Approach for Two-Level Planarization
11th Int. Symposium on Graph Drawing, GD 2003, LNCS 2912, Springer, 2004 		Petra Mutzel
  Marko Tosic M. Eiglsperger, M. Siebenhaller, M. Kaufmann:
An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Carsten Gutwenger
01.02.2005 Martin Schulte-Hobein M. Forster:
A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Carsten Gutwenger
  Müjdat Cagliyan U. Dogrusoz, E. Giral, A. Cetintas, A. Civrill, E. Demir:
A Compound Graph Layout Algorithm for Biological Pathways
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Karsten Klein
  Sebastian Kaps M. Raitner:
Visual Navigation of Compound Graphs
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Karsten Klein
  Sebastian Sondern J. Boyer, W. Myrvold:
On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
Journ. of Graph Algorithms and Applications (JGAA) 		Carsten Gutwenger
08.02.2005 Roman Klinger C. Gutwenger, P. Mutzel:
Graph Embedding with Minimum Depth and Maximum External Face
11th Int. Symposium on Graph Drawing, GD 2003, LNCS 2912, Springer, 2004 		Carsten Gutwenger
  Sebastian Steinfort E. Gansner, Y. Kren, S. North:
Graph Drawing by Stress Majorization
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Markus Chimani
  Erdal Yigit S. Hachul, M. Jünger:
Drawing Large Graphs with a Potential Field Based Multilevel Algorithm
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Markus Chimani
  Töresin Karakoyun S. Kobourov, R. Yusufov:
Visualizing Large Graphs with Compound-Fisheye Views and Treemaps
12th Int. Symposium on Graph Drawing, GD 2004, LNCS, Springer, to appear 2005 		Karsten Klein

Themengebiet

Das Gebiet des Automatischen Zeichnens von Graphen beschäftigt sich mit Design, Analyse, Implementierung und experimenteller Evaluierung von Algorithmen zum automatischen Layout von diskreten Strukturen auf der Ebene (oder im dreidimensionalen Raum). Anwendungen beinhalten Datenbankvisualisierungen, Datenmodelle im Businessbereich, UML-Klassendiagramme im Software-Engineering, Netzwerke in der Bioinformatik, sowie Entwurf und Analyse von Netzen in der Elektrotechnik.

Kriterien für eine leicht verständliche (oder auch ästhetisch schöne) Zeichnung sind nach wahrnehmungspsychologischen Studien unter anderen: wenige Überkreuzungen zwischen Kanten, möglichst große Winkel zwischen den zu einem Knoten adjazenten Kanten, oder wenige Knicke in Kanten, die in einer orthogonalen Zeichnung aus horizontalen und vertikalen Segmenten bestehen.

Inhalt des Seminars

Thema des Seminars sind ausgewählte Algorithmen zum Zeichnen von allgemeinen Graphen und Digraphen sowie von Spezialklassen wie etwa von Bäumen oder von planaren Graphen. Wir behandeln in dem Seminar neueste algorithmische Forschungsergebnisse, die auf den Internationalen Graph Drawing Symposien GD 2003 und GD 2004 veröffentlicht wurden.

Vorkenntnisse

Neben den Grundlagen des Gebiets Algorithmen und Datenstrukturen werden keine besonderen Vorkenntnisse erwartet.

Anmeldung

Die Voranmeldung zur Vorbesprechung sollte bis zum 15. Dezember via Email erfolgen: <petra.mutzel gif .cs.uni-dortmund.de>.
Die Vorbesprechung fand am 20.12.2004 statt.

Literatur

Aktuelle Originalarbeiten, z.B. in Lecture Notes in Computer Science 2912, Springer-Verlag, Liotta, G. (Ed.), Graph Drawing, 11th International Symposium, GD 2003, Perugia, Italy, 2004 oder auch www.gd2004.org.

<webmaster  ls11.cs.tu-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten