Abstract
Let G be any n-vertex planar graph. It is proved 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 than 22** one-half n** one-half vertices. An algorithm is exhibited which finds such a partition A, B, C in O(n) time.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 177-189 |
| Number of pages | 13 |
| Journal | SIAM J Appl Math |
| Volume | 36 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jan 1 1979 |
All Science Journal Classification (ASJC) codes
- Applied Mathematics
Fingerprint Dive into the research topics of 'SEPARATOR THEOREM FOR PLANAR GRAPHS.'. Together they form a unique fingerprint.
Cite this
Lipton, R. J., & Tarjan, R. E. (1979). SEPARATOR THEOREM FOR PLANAR GRAPHS. SIAM J Appl Math, 36(2), 177-189. https://doi.org/10.1137/0136016