SEPARATOR THEOREM FOR PLANAR GRAPHS.

Richard J. Lipton, Robert Endre Tarjan

Research output: Contribution to journalArticle

839 Scopus citations

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 languageEnglish (US)
Pages (from-to)177-189
Number of pages13
JournalSIAM J Appl Math
Volume36
Issue number2
DOIs
StatePublished - 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