Monday March 7th at 4.30pm

In 1977, Lipton and Tarjan proved that every planar graph on n vertices has a separator of O(n

found applications in numerous areas including approximation algorithms for NP-hard problems, solving sparse systems of linear

equations, pebbling games, and graph drawing. In 1990, Alon, Seymour and Thomas generalised the Lipton-Tarjan result by proving that

every graph with a fixed excluded minor (eg planar graphs have no K

Unfortunately, the running time of the resulting algorithm was O(n

step to the Alon-Seymour-Thomas algorithm which leads to a O(n) time algorithm, at the expense of a slightly larger separator. This is joint

work with Bruce Reed.