Algorytmy na grafach planarnych

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.