Wiele problemów grafowych, dla których istnieją algorytmy wielomianowe, można
rozwiązywać w czasie bliskim liniowego jeśli dany graf jest planarny. Na
przykład, minimalne cięcie rozdzielające dane dwa wierzchołki w planarnym
grafie nieskierowanym może być znalezione w czasie O(nlog(n)), podczas gdy
czas działania najlepszego znanego algorytmu dla dowolnego grafu
nieskierowanego to O(n^3). Celem wykładu jest zapoznanie studentów z
technikami używanymi do konstruowania efektywnych algorytmów dla grafów
planarnych, między innymi:
1. Kombinatoryczna definicja grafu planarnego.
2. Dualność.
3. Separatory.
4. Najkrótsze ścieżki dla nieujemnych wag krawędzi.
5. Najkrótsze ścieżki z wielu źródeł.
6. Najkrótsze ścieżki dla dowolnych wag krawędzi, własność Monge'a.
7. Dense distance graph (DDG), najkrótsze ścieżki w DDG.
8. Wyrocznie aproksymujące odległość.
9. Diagramy Voronoi'a dla grafów planarnych i wyrocznie odległości.
10. Minimum st cut w grafie nieskierowanym.
11. Maximum st flow w grafie skierowanym.
12. Techniki aproksymacyjne dla grafów planarnych: branchwidth, treewidth, technika Baker.
13. Aproksymacja TSP w grafie planarnym.
