iconOptimization Algorithms for Planar Graphs

by Philip Klein (please email me using lastname at brown.edu to receive notifications when more complete drafts become available or to make suggestions for edits.  I have not yet included historical notes describing the origins of the techniques described here.)

Rooted forests and trees
Basic graph definitions
Elementary graph theory
Planar embedded graphs
Separators in planar graphs
Shortest paths with nonnegative lengths
Multiple-source shortest paths
Shortest paths with negative lengths
Single-source, single-sink max flow
Multiple-source, multiple-sink max flow
Approximate distance queries
Primal-dual method for approximation algorithms
Branchwidth and local approximation schemes
Approximation scheme for the traveling salesman problem
Approximation schemes for subset TSP and Steiner tree
Brick decomposition
Structure Theorem for Steiner tree

Appendix: Splay trees and link-cut trees