Vorlesungen Fundamental Algorithms (CSE) Effiziente Algorithmen und Datenstrukturen I Randomisierte Algorithmen Algorithmen für die Speicherhierarchie Fortgeschrittene Netzwerk- und Graph-Algorithmen Proseminar Graph Drawing Hauptseminar Inside Google: Algorithmik von Suchmaschinen Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

Proseminar: Graph Drawing

Dienstags 14:00-15:30 Uhr im Raum 03.11.018

[Zusammenfassung] [Themenliste] [Anmeldung] [Vorbesprechung] [Termine] [Hinweise] [Links]

Zusammenfassung

Das Visualisieren struktureller Information ist für das Verständnis komplexer Zusammenhänge von entscheidender Bedeutung. Beispiele in der Informatik sind das Visualisieren von Datenbankmodellen in CASE-Tools, eine graphische Darstellung der Zustandsübergänge bei Automaten oder das Data-Mining. Graphen sind ein ideales Hilfsmittel, um strukturelle Information abstrakt zu modellieren. Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Eine Kante verläuft dabei zwischen zwei Knoten und beschreibt eine Beziehung zwischen diesen Knoten.
	Eine Zeichnung eines Graphen ist eine Darstellung dieser Beziehungen als Diagramm. Sie ordnet den Knoten Symbole (etwa Kreise oder Rechtecke) und Koordinaten (meist in der euklidischen Ebene) zu. Die Kanten werden durch Kurven zwischen den zugehörigen Knotensymbolen dargestellt. Beispiele für erlaubte Kurven sind Polygonzüge, orthogonale Polygonzüge oder Geradensegmente.
Graphenzeichnungen sollen vor allem zwei Anforderungen genügen: Sie sollen ``schön'' sein, aber auch die strukturellen Zusammenhänge der zugrundeliegenden Daten herausarbeiten. Es ist klar, dass manche Zeichnungen die enthaltene Information besser zum Ausdruck bringen als andere. Deshalb werden ästhetische Kriterien festgelegt, welche die Lesbarkeit von Graphen erhöhen sollen. Man kann etwa verlangen, dass Symmetrien oder Cluster in einem Graphen sichtbar werden oder dass die Anzahl der Schnittpunkte von Kanten möglichst klein ist. Diese Kriterien sind jedoch subjektiv und kontextabhängig. Sind die Anforderungen an die Darstellung einer Klasse von Graphen einmal festgelegt, dann versucht man, effiziente Algorithmen zu entwickeln, die möglichst gute Zeichnungen automatisch liefern.
	In diesem Proseminar sollen in den einzelnen Vorträgen grundlegende Ergebnisse aus diesem aktiven Forschungsgebiet vorgestellt werden. Es werden zuerst Algorithmen für das Zeichnen von Bäumen untersucht. Dann wird der Frage nachgegangen, wann sich ein Graph ohne Überschneidungen von Kanten zeichnen lässt. Für den Fall, dass; letzteres nicht möglich ist, werden Algorithmen angewendet, die die Zahl der Kantenkreuzungen zumindest klein halten. Neben einigen weiteren Graphklassen und -algorithmen werden zudem aktuelle Anwendungen vorgestellt.

Themenliste:

Einführung: Wie zeichnet man einen Graphen?
Schöne Zeichnungen von Bäumen
Zeichnungen von Binärbäumen mit optimaler Fläche
Das Feder-Modell zum Zeichnen beliebiger Graphen
Hierarchische Zeichnungen
Testen eines Graphen auf Planarität
Ein einfacher Algorithmus für das Zeichnen planarer Graphen
Planarisierung von Graphen
Färben von Landkarten (planare Graphen)
Minimierung von Kantenkreuzungen bei allgemeinen Graphen
3-D Zeichnungen von Graphen

Eine Themenliste mit Literaturangaben wird nachgereicht.

Interessentinnen/en können sich bei der Vorbesprechung oder vorab per Email an baumgart@in.tum.de mit Subject "Graph Drawing (Anmeldung)" anmelden. In der E-Mail sollen folgende Informationen enthalten sein:

Name, Vorname
Studiengang und Studienfach
Semester
E-Mail (nur Adressen @in.tum.de)
bevorzugtes Thema

Vorbesprechung

Die Vorbesprechung findet am 19.07.2007, 15:00 Uhr s.t. im Raum MI 03.11.018 statt.

Termine und Betreuer

Das Proseminar findet am 11. Dezember von 14:00 (s.t.) Uhr bis ca. 16:15 Uhr im Raum 03.11.018 statt.

	`Ruoruo Du` Zeichnungen von Binärbäumen mit optimaler Fläche (Thema 3) Betreuer: Johannes Nowak
	`Ilya Krasnov` Das Feder-Modell zum Zeichnen beliebiger Graphen (Thema 4) Betreuer: Matthias Baumgart
	`Konstantin Govedarski` Planarisierung von Graphen (Thema 8) Betreuer: Stefan Eckhardt

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung)	Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit. Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität)	Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität)	Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).
Anwesenheit bei den Vorträgen	Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung m¨ssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortrag		erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem Vortrag		Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem Vortrag		Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortrag		fertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:

Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).

Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:

Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.

Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)

Interessante Links

Die Grundlagen für das Zeichen von Graphen von Isabel F. Cruz und Roberto Tamassia (farbige, gezippte PostScript-Datei, 80995 Bytes).

Ein gute Übersicht über Algorithmen für das Zeichnen von Graphen von Roberto Tamassia (gezippte PostScript-Datei, 106454 Bytes).

Jede Menge Hyperlinks über Theorie und Praxis des Graph-Drawing.

Buch: Reinhard Diestel, Graphentheorie, 2. Auflage, Springer, 2000. ( Webseite mit elektronischer Ausgabe )

Weitere Auskünfte bei Matthias Baumgart