## 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.