- 3.3. Planar graph separators:
- Lipton-Tarjan's theorem and algorithm
- 3.4. Applications:
- improvements of Maximum Independent Set, shortest paths in O(n) time.
- 3.5. Graph separators in higher dimensions?
-
- -- TD:
- graphs separators with application to
efficient point location in planar triangulations (code provided
for encoding the triangulation).
Steve Y. Oudot
2009-03-27