ICS Theory Group

February 27 , Winter 2009: Theory Seminar

1:00pm in 253 ICS

A Separator Theorem For Planar Graphs

By Richard Lipton and Robert Tarjan

Presented by Lowell Trott, UC Irvine

Let G be any n-vertex planar graph. It will be shown that the vertices of G can be partitioned into three sets A,B,C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more that 2v(2n) vertices. An algorithm will be presented which finds such a partition in O(n) time.