Modul

Siehe Teilleistung

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.

Siehe Teilleistung

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.

2 SWS Vorlesung, 1 SWS Übung, 5 LP entspricht 150h aufgeteilt in

30h Vorlesungsbesuch
15h Übung
40h Nachbereitung
25h Lösen der Übungsaufgaben
40h Prüfungsvorbereitung