Dozenten: Mathias Schacht und Dirk Schlatter
Termine
Beginn der Vorlesung: 13. April.| VL | Mittwoch | 09:00 - 11:00 | (RUD 26, 1.308) |
|---|---|---|---|
| Freitag | 09:00 - 11:00 | (RUD 26, 1.305) | |
| UE | Mittwoch | 15:00 - 17:00 | (RUD 26, 1.308) |
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Inhalte und Lernziele
Planare Graphen sind Graphen, welche sich in der Ebene darstellen lassen, ohne dass sich zwei Kanten "kreuzen". Die Vorlesung gliedert sich in einen theoretischen, einen algorithmischen, sowie einen vertiefenden Abschnitt.
Der ersten Teil führt zunächst einige grundlegende graphentheoretische Begriffe ein, und gibt einen kurzen Abriss der im weiteren benötigten topologischen Konzepte und Resultate. Den Schwerpunkt bilden dann die Beweise der klassischen Sätze von Euler und Kuratowski, die Betrachtung von dualen Graphen, sowie algebraische Charakterisierungen. Abschließend wird noch auf die Dekomposition entlang der Zusammenhangsstruktur eingegangen, welche zu den algorithmischen Fragestellungen überleitet.
Im zweiten Teil stehen zunächst verschiedene effiziente Planaritätstests (Booth & Luecker, Hopcroft & Tarjan, Hsu & Shi) im Mittelpunkt. Mit Hilfe des Konzeptes der beschränkten Baumweite wird dann ein Ansatz von Eppstein vorges tellt, der u.a. einen linearen Algorithmus für das Untergraphenproblem liefert.
Für den dritten Teil wird ein Thema, in Absprache mit den Studierenden, aus einigen zuvor angesprochenen ausgewählt und weiter vertieft. Diese sind, noch ohne Gewähr, Kreuzungszahlen, Graphen höheren Geschlechts, zufällige planare Graphen, Enumeration von planaren Graphen, maximale planare Subgraphen und der Vierfarbensatz.
Voraussetzungen
- Abschluß des Grundstudiums in Informatik
- Vorlesungen "Graphen und Algorithmen 1/2" von Vorteil, aber nicht notwendig
Übungen
Während des theoretischen Teils der Vorlesung sind Übungsaufgaben zu bearbeiten, deren Lösung dann in den Übungen besprochen wird. Im algorithmischen Teil sollen einige der angesprochenen Algorithmen implementiert werden, wozu individu elle Programmieraufgaben vergeben werden. In beiden Phasen ist Gruppenarbeit von zwei Personen zulässig. Die Vergabe des Übungsscheins erfolgt, wenn insgesamt mehr als 60% der Punkte erreicht werden.
Erstes Übungsblatt (Abgabetermin: 29.April)
Zweites Übungsblatt (Abgabetermin: 13. Mai)
Musterlösung zur Transitivtät der Minorenrelation (2.Blatt, A3).
Drittes Übungsblatt (Abgabetermin: 24. Mai)
Viertes Übungsblatt (Abgabetermin: 14. Juni)
Fünftes Übungsblatt (Abgabetermin: 15. Juli)
Prüfungen
mündlich (Voraussetzung: Übungsschein, Termin in Absprache)Skript
Ein ausführliches Skript zum ersten Teil der Vorlesung (ohne Beweise) gibt es hier als pdf-Datei.Literatur
- , Einführung in Graphen und Algorithmen, (6. Kapitel)
- , Graphentheorie, (4. Kapitel)
- , Graphs on Surfaces, John Hopkins University Press, 2001
English