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