Algorithmen zum Zeichnen von Graphen WS 2006/2007

Allgemeines

Dozent

Die Vorlesung wird von Prof. Dr. Franz J. Brandenburg durchgeführt.

Voraussetzungen

Die Vorlesung richtet sich an Studenten im Hauptstudium des Diplom- oder Masterstudiengangs Informatik. Ein vorheriger Besuch der Vorlesung "Effiziente Algorithmen" ist von Vorteil, aber keine Voraussetzung.

Anrechenbarkeit (für Diplomstudiengang)

Säule I, Vertiefungsgebiet "Effiziente Algorithmen"

Termine

• Vorlesung: Mo 10:00-12:00 (HS 12 IM), Di 10:00-11:00 (HS 12 IM)
• Übung: Mi 14:00-15:30 (R 004 ITZ), Mi 15:30-17:00 (R 004 ITZ)

Inhalte

"Ein Bild sagt 1000 Worte". Komplexe Informationen lassen sich oft wesentlich besser vermitteln, wenn sie als Zeichnung vorliegen. Im Zeichnen von Graphen ("Graph Drawing") beschäftigt man sich mit dem Problem, zu einem gegeben Graphen (also einer Menge von Knoten und Kanten und evtl. Zusatzinformationen) eine "schöne" Zeichnung zu erstellen.

In dieser Vorlesung werden Algorithmen zum Zeichnen folgender Graphklassen vorgestellt und untersucht:

• Bäume
• Gerichtete azyklische Graphen
• Allgemeine Graphen
• Planare Graphen

Literatur

Hauptliteratur für die Vorlesung sind folgende Bücher:

• M. Kaufmann, D. Wagner (Hrsg.), Drawing Graphs - Methods and Models, LNCS 2025, Springer Verlag, 2001, Signatur: 80/SS 4800-2025 [online]
• G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis, Graph Drawing - Algorithms for the Visualization of Graphs, Prentice Hall, 1999, Signatur: 80/ST 300 D543
• K. Sugiyama, Graph Drawing and Applications for Software and Knowledge Engineers, Series on Software Engineering & Knowledge Engineering, World Scientific, 2002, Signatur: 80/ST 300 S947

Detaillierte ergänzende Informationen finden sich vor allem in den Konferenzbänden der "Graph Drawing"-Konferenz:

• Proc. Graph Drawing 1994, LNCS 894, Springer, 1995, Signatur: 80/SS 4800-894
• Proc. Graph Drawing 1995, LNCS 1027, Springer, 1996, Signatur: 80/SS 4800-1027
• Proc. Graph Drawing 1996, LNCS 1190, Springer, 1997, Signatur: 80/SS 4800-1190
• Proc. Graph Drawing 1997, LNCS 1353, Springer, 1998, Signatur: 80/SS 4800-1353
• Proc. Graph Drawing 1998, LNCS 1547, Springer, 1998, Signatur: 80/SS 4800-1547 [online]
• Proc. Graph Drawing 1999, LNCS 1731, Springer, 1999, Signatur: 80/SS 4800-1731 [online]
• Proc. Graph Drawing 2000, LNCS 1984, Springer, 2001, Signatur: 80/SS 4800-1984 [online]
• Proc. Graph Drawing 2001, LNCS 2265, Springer, 2002, Signatur: 80/SS 4800-2265 [online]
• Proc. Graph Drawing 2002, LNCS 2528, Springer, 2002, Signatur: 80/SS 4800-2528 [online]
• Proc. Graph Drawing 2003, LNCS 2912, Springer, 2004, Signatur: 80/SS 4800-2912 [online]
• Proc. Graph Drawing 2004, LNCS 3383, Springer, 2005, Signatur: 80/SS 4800-3383 [online]
• Proc. Graph Drawing 2005, LNCS 3843, Springer, 2006, Signatur: 80/SS 4800-3843 [online]

Die Online-Versionen sind nur aus dem Uni-Netz nutzbar.

Vorlesungsunterlagen (nur innerhalb des Uni-Netzes zugreifbar)

Übungsblätter (nur innerhalb des Uni-Netzes zugreifbar)