Applications of a planar separator theorem

Hichard J. Lipton, Robert Endre Tarjan

Research output: Contribution to journalConference articlepeer-review

83 Scopus citations


Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only 0(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

Original languageEnglish (US)
Pages (from-to)162-170
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1977
Externally publishedYes
Event18th Annual Symposium on Foundations of Computer Science, SFCS 1977 - Providence, United States
Duration: Oct 31 1977Nov 2 1977

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • Algorithm
  • Boolean circuit complexity
  • Divide-and-conquer
  • Geometric complexity
  • Graph embedding
  • Lower bounds
  • Maximum independent set
  • Non-serial dynamic programming
  • Pebbling
  • Planar graphs
  • Separator
  • Space-time tradeoffs


Dive into the research topics of 'Applications of a planar separator theorem'. Together they form a unique fingerprint.

Cite this