Applications of a planar separator theorem

Hichard J. Lipton, Robert Endre Tarjan

Research output: Contribution to journalConference articlepeer-review

75 Scopus citations

Abstract

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
Volume1977-October
DOIs
StatePublished - Jan 1 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

  • Computer Science(all)

Keywords

  • 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

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

Cite this