Planar Graph TSP is the problem of finding the shortest tour that visits all
vertices of a planar unweighted graph at least once. The talk will present a
polynomial time approximation scheme (PTAS) for this problem developed
by Grigni, Koutsoupias and Papadimitriou (presented in 1995 FOCS).
The approximation scheme uses a planar separator theorem to divide the
graph into subproblems. We will discuss the
proof of the original planar separator theorem and several
modifications that allow it to be used for this problem.