|Discrete Mathematics and Optimization Seminar
Monday March 7th at 4.30pm
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(n1/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 K5 and no K3,3 minor) has a separator of O(n1/2) vertices.
Unfortunately, the running time of the resulting algorithm was O(n3/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.