Discrete Mathematics and Optimization Seminar

---

DAVID WOOD
McGill University
Monday March 7th at 4.30pm
Burnside 1205



Title. Fast Separation in Graphs with an Excluded Minor.

Abstract. A separator in a graph is a set of vertices whose removal splits the graph into two roughly equal sized pieces.
In 1977, Lipton and Tarjan proved that every planar graph on n vertices has a separator of O(n^1/2) vertices. This result has
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₅ and no K_3,3 minor) has a separator of O(n^1/2) vertices.
Unfortunately, the running time of the resulting algorithm was O(n^3/2), compared to O(n) in the planar case. We present a preprocessing
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.