Algorithms for Planar Graphs (Algorithms & Theory Seminar)
- Module 3 Master's Seminar
- ECTS: 3 CP
- Instructors: Dirk Oliver Theis, Abdullah Makkeh.
A graph is planar if it can be drawn in the plane without crossing edges. This nice property has tons of algorithmic consequences. First of all, it rise questions like "How can an algorithm recognize whether a graph is planar?", "How can I draw a planar graph?". But there are also lots of algorithmic problems for which planar graphs allow better solutions: faster (even polynomial vs NP-hard), or simpler.
The typical presentation in this seminar will cover one algorithm for planar graphs. The attendees have two choices:
- present proofs of correctness for the algorithm (Theory branch)
- implement the algorithm!
At the beginning of the term, there will be 2-3 lectures to cover some basics which are too boring for a presentation: What's a planar graph? What's a planar map? @hat are faces? Euler's formula; The dual graph.
Here is a preliminary list of possible presentations. (It get's vague at the more difficult topics near the end of the list.)
- Sampling a uniformly random planar map1
- 5-Coloring planar graphs (very easy)
- Kuratowski's theorem (no algorithm, just theorem)
- Planar graph recognition and drawing (several algorithms = several presentations)
- Random planar graphs--the random planar graph process2 [code requires code for #3]
- Dynamic planar embedding algorithm of dynamic graphs3
- Geometry: 3-connected planar graphs are 3-dimensional polytopes! (no code)
- Cycles and Cuts. Polynomial time Max-Cut algorithm.
- The separator algorithm (super important: allows for recursive algorithm on planar graphs)
- Linear time shortest paths--similar to Dijkstra, just better (long)
- More shortest paths algorithms
- Approximate distance queries
- Several Approximation algorithms
It is particularly important to implement topic #1: It will generate the random planar maps which the other graph algorithm codes will take as input.
Most of the topics are in this book: http://www.planarity.org/.
1) See this paper.
2) See this paper. Easy topic, if you just want to code the algorithm (+ visualization); difficult topic if you want to present the proof!
3) See this paper.