Talk:Algorithms Seminar/Spring10

What is a separator theorem for a family of graphs: motivate the question via divide and conquer
some examples of separator theorems (trees, grids, outerplanar graphs (via duality))
sparsity is not enough (Erdos/Graham/Szemeredi)
Proof: from Erickson notes
- If balanced cycle separator doesn't exist, then the cycle is "fat" inside.
- this would require too many vertices.
this doesn't give construction though: Klein notes provide an actual algorithm.
Miller separator is an edge separator, and also works for weaker-connectivity graphs (LT requires 3-connectedness)

Contents