The World is Flat: Algorithms for Classical Optimization Problems Restricted to Planar Graphs
March 28, 2012

Maximum flow, shortest paths, traveling salesman, Steiner tree, multiterminal cut---for such well-studied graph problems, one might think nothing new can be said. However, when the input is restricted to planar graphs, new techniques become applicable, leading to nearly linear-time exact algorithms for some of the problems and nearly linear-time approximation schemes for others. The talk will survey some of the recent developments on these problems and indicate some of the techniques involved.