The world is flat: algorithms for classical optimization problems restricted to planar graphs

For a variety of classical optimization problems in graphs---e.g., maximum
flow, shortest paths, traveling salesman, Steiner tree, and
multiterminal cut---new techniques become applicable when the input
graph is restricted to be planar. Under the restriction,
approximation schemes become possible for problems that are APX-hard
in general. Linear-time algorithms or near-linear-time algorithms
emerge for problems for which no such fast algorithms are yet known
for general graphs. This talk will survey some of the recent
developments on these problems and indicate some of the techniques
involved.