iconOptimization Algorithms for Planar Graphs

by Philip Klein and Shay Mozes (please email us to receive notifications when more complete drafts become available or to make suggestions for edits.  We have not yet included historical notes describing the origins of the techniques described here.)

Book Draft

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
Shortest paths in dense distance graphs
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 Steiner problems (partial)
Brick decomposition
Approximation Schemes for some problems with optional connectivity
Appendix: Splay trees and link-cut trees