Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
Automatisches Zeichnen von Graphen

Automatisches Zeichnen von Graphen

(Spezialvorlesung 042391, DPO Informatik)

Wintersemester 2007/2008

Prof. Dr. Petra Mutzel

Termin:   
Montag12:15 - 14:00OH14, Raum 304
Dienstag12:15 - 14:00OH14, Raum 304
Beginn:15.10.2007

Siehe auch: Übungen Automatisches Zeichen von Graphen

Zugangsvoraussetzungen

Vordiplom, hilfreich ist die VO Effiziente Algorithmen und Komplexitaetstheorie

Kommentar

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.

Neben Algorithmen zum Zeichnen von allgemeinen Graphen und Digraphen werden wir auch Zeichenmethoden zum Zeichnen für Spezialklassen von Graphen behandeln, wie etwa von Bäumen, von planaren Graphen oder von Graphen mit Maximalgrad vier. Alle diese Verfahren behandeln das Zeichnen auf einer 2-dimensionalen Ebene, gegen Ende der Vorlesung werden wir Ausblicke zum Zeichnen in 3 Dimensionen geben. Die Methoden hierbei sind vielfältig und beinhalten sowohl einfache Algorithmen und Datenstrukturen (wie z.B. scan-line) sowie komplexe Graphenalgorithmen (z.B. lineare Planaritätstests, Netzwerkflussverfahren) und Optimierungsverfahren (z.B. Schnittebenenverfahren).

Vermittelte Fähigkeiten

  • Analyse und Modellierung von Problemen
  • selbständige Implementierung einiger Zeichenverfahren
  • Einblick in die Graphentheorie, Graphenalgorithmen, Optimierungsverfahren

Schwerpunktgebiete

  • 4. Algorithmen, Komplexität und formale Modelle
  • 6. Computational Intelligence und Natural Computing
  • 7. Intelligente Systeme

Literatur

Aktuelle Originalarbeiten, z.B.in Lecture Notes in Computer Science 4372, Springer-Verlag,
Kaufmann, M. und Wagner, D.(Eds.), Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, 2007
oder auch GD2007, Sydney (siehe hier),
oder auch Mutzel, P. und Jünger, M.: Graph Drawing Software, Springer, Berlin 2003. (Kapitel Technical Foundations)

Links

OGDF Homepage
Graphen-Editor GDE

Folien und Vorlesungsmitschriften

Die Folien zur Vorlesung gibt es jeweils in zwei Versionen: mit 1 Folie pro Seite (zum Anschauen) und mit 6 Folien pro Seite (zum Ausdrucken).

Einführung
     
(15.10/16.10 VO 1,2) Intro GD Teil 1, Teil 2
[1 Folie/Blatt]
Intro GD Teil 1, Teil2
[6 Folien/Blatt]
 
       
Zeichnen von Bäume      
(16.10/22.10 VO 2,3) Tree Drawing
[1 Folie/Blatt]
Tree Drawing
[6 Folien/Blatt]
 
       
Hierarchische Zeichenverfahren      
(29.10/30.10 VO 4,5) Sugiyama
[1 Folie/Blatt]
Sugiyama
[6 Folien/Blatt]
Zusatzmaterial zu Sugiyama
(5.11/6.11 VO 6,7) Zählen von Kreuzungen Teil 1, Teil 2
[1 Folie/Blatt]
Zählen von Kreuzungen Teil 1, Teil 2
[6 Folien/Blatt]
 
(6.11/12.11/13.11
VO 8,9,10)
Kreuzungsminimierung Teil 1, Teil 2 (update)
[1 Folie/Blatt]
Kreuzungsminimierung Teil 1, Teil 2 (update)
[6 Folien/Blatt]
 
(19.11/20.11 VO 11,12) Kreuzungsminimierung Exakt
[1 Folie/Blatt]
Kreuzungsminimierung Exakt
[6 Folien/Blatt]
 
(20.11/26.11/27.11
VO 12,13,14)
Koordinatenzuweisung (update)
[1 Folie/Blatt]
Koordinatenzuweisung (update)
[6 Folien/Blatt]
 
       
Planare Zeichenverfahren      
(16.10 VO 2) Animation Planarisierung
[Power Point Datei]
   
(3.12/4.12 VO 15,16) Planaritätstest Teil 1, Teil 2
[1 Folie/Blatt]
Planaritätstest Teil 1, Teil 2
[6 Folien/Blatt]
 
(27.11/10.12/11.12
VO 14,17,18)
Planar Straightline
[1 Folie/Blatt]
Planar Straightline
[6 Folien/Blatt]
 
(17.12 VO 19) SPQR-Bäume und planare Einbettungen
[1 Folie/Blatt]
SPQR-Bäume und planare Einbettungen
[6 Folien/Blatt]
 
(18.12 VO 20) Planare Einbettungen mit max. Außenfläche
[1 Folie/Blatt]
Planare Einbettungen mit max. Außenfläche
[6 Folien/Blatt]
 
(7.1 VO 21) Einbettungs-Constraints
[1 Folie/Blatt]
Einbettungs-Constraints
[6 Folien/Blatt]
 
(8.1 VO 22) Optimales Kanteneinfügen
[1 Folie/Blatt]
Optimales Kanteneinfügen
[6 Folien/Blatt]
 
(21.1 VO 23) Planaritätsbasierte Verfahren
[1 Folie/Blatt]
Planaritätsbasierte Verfahren
[6 Folien/Blatt]
 
(21.1/22.1 VO 23,24) Orthogonale planare Verfahren
[1 Folie/Blatt]
Orthogonale planare Verfahren
[6 Folien/Blatt]
 
       
Kräftebasierte Verfahren      
(28.1/29.1 VO 25,26) Kräftebasierte Verfahren
[1 Folie/Blatt]
Kräftebasierte Verfahren
[6 Folien/Blatt]
 
(4.2/5.2 VO 27,28) Kräftebasierte Verfahren für große Graphen
[1 Folie/Blatt]
Kräftebasierte Verfahren für große Graphen
[6 Folien/Blatt]
 
       
Quad Tree      
(4.2 VO 27) Quad Trees
[1 Folie/Blatt]
Quad Trees
[6 Folien/Blatt]
 
<webmaster  ls11.cs.tu-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten