Veranstaltung

Weiterführende Literatur

Takao Nishizeki and Norishige Chiba. Planar Graphs: Theory and Algorithms, volume 32 of Annals of Discrete Mathematics. North-Holland, 1988.

Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden, ohne dass die Kanten sich kreuzen. Planare Graphen haben viele schöne Eigenschaften, die benutzt werden können um für zahlreiche Probleme besonders einfache, schnelle und schöne Algorithmen zu entwerfen. Oft können sogar Probleme, die auf allgemeinen Graphen (NP-)schwer sind auf planaren Graphen sehr effizient gelöst werden. In dieser Vorlesung werden einige dieser Probleme und Algorithmen zu ihrer Lösung vorgestellt.

Lernziele:
Die Teilnehmer besitzen einen vertieften Einblick in die theoretischen Aspekte und algorithmischer Grundlagen im Gebiet der planaren Graphen. Sie kennen zentrale Konzepte und Techniken zur Behandlung algorithmischer Fragestellungen auf planaren Graphen und können diese erläutern. Dabei nutzt der/die Studierende das Wissen aus der Vorlesung welches in Teilen auf bestehendem Wissen aus den Themenbereichen Graphentheorie und Algorithmik fußt. Außerdem kann er/sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungstehmen im Bereich planare Graphen interpretieren und nachvollziehen.

Studierende sind außerdem in der Lage die besonderen strukturellen Unterschiede zwischen allgemeinen Graphen und planaren Graphen zu erörtern. Sie können weiterhin erläutern wie sich diese speziellen Eigenschaften planarer Graphen auf die Laufzeit von Algorithmen auswirken. Insbesondere ist es ihm/ihr möglich zu erläutern warum einige Algorithmen für planaren Graphen korrekt sind und eine polynomielle Laufzeit haben, während sie für allgemeine Graphen entweder nicht das korrekte Ergebnis produzieren oder eine deutlich schlechtere Laufzeit haben. Das gilt im Besonderen für Probleme für die kein Algorithmus mit polynomieller Laufzeit für allgemeine Graphen bekannt ist, die aber auf planaren Graphen in Polynomialzeit lösbar sind. Dieses Wissen können die Teilnehmer nutzen um algorithmische Probleme für planare Graphen zu identifzieren, auf ihren algorithmischen Kern reduzieren und anschließend formal formulieren.

Empfehlungen:
Kenntnisse zu Grundlagen der Graphentheorie und Algorithmentechnik sind hilfreich.

Arbeitsaufwand: Vorlesung und Übung mit 3 SWS, 5 LP
5 LP entspricht ca. 150 Arbeitsstunden, davon
ca. 45 Std. Besuch der Vorlesung und Übung,
ca. 25 Std. Vor- und Nachbereitung,
ca. 40 Std. Bearbeitung der Übungsblätter,
ca. 40 Std. Prüfungsvorbereitung.

Nähere Informationen unter http://i11www.iti.uka.de/teaching.

Die Lehrveranstaltung wird unregelmäßig angeboten.