A Separator Theorem for Planar Graphs.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Let G be any n-vertex planar graph. Prove 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 2n3 vertices, and C contains no more than 2sq.rt 2sq. rt n vertices. An algorithm is exhibited which finds such a partition A, B, C in on time.
- Theoretical Mathematics