Applications of a planar separator theorem

Hichard J. Lipton; Robert Endre Tarjan

doi:10.1109/sfcs.1977.6

Applications of a planar separator theorem

Hichard J. Lipton, Robert Endre Tarjan

Research output: Contribution to journal › Conference article › peer-review

85 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 language	English (US)
Pages (from-to)	162-170
Number of pages	9
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1977-October
DOIs	https://doi.org/10.1109/sfcs.1977.6
State	Published - 1977
Externally published	Yes
Event	18th Annual Symposium on Foundations of Computer Science, SFCS 1977 - Providence, United States Duration: Oct 31 1977 → Nov 2 1977

All Science Journal Classification (ASJC) codes

General Computer Science

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

Access to Document

10.1109/sfcs.1977.6

Cite this

@article{5eaa464e2e8643f8a88125ef73a14b83,

title = "Applications of a planar separator theorem",

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.",

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",

author = "Lipton, \{Hichard J.\} and Tarjan, \{Robert Endre\}",

note = "Publisher Copyright: {\textcopyright} 1977 IEEE Computer Society. All rights reserved.; 18th Annual Symposium on Foundations of Computer Science, SFCS 1977 ; Conference date: 31-10-1977 Through 02-11-1977",

year = "1977",

doi = "10.1109/sfcs.1977.6",

language = "English (US)",

volume = "1977-October",

pages = "162--170",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - Applications of a planar separator theorem

AU - Lipton, Hichard J.

AU - Tarjan, Robert Endre

PY - 1977

Y1 - 1977

N2 - 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.

AB - 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.

KW - Algorithm

KW - Boolean circuit complexity

KW - Divide-and-conquer

KW - Geometric complexity

KW - Graph embedding

KW - Lower bounds

KW - Maximum independent set

KW - Non-serial dynamic programming

KW - Pebbling

KW - Planar graphs

KW - Separator

KW - Space-time tradeoffs

UR - https://www.scopus.com/pages/publications/85035070413

UR - https://www.scopus.com/inward/citedby.url?scp=85035070413&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1977.6

DO - 10.1109/sfcs.1977.6

M3 - Conference article

AN - SCOPUS:85035070413

SN - 0272-5428

VL - 1977-October

SP - 162

EP - 170

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - 18th Annual Symposium on Foundations of Computer Science, SFCS 1977

Y2 - 31 October 1977 through 2 November 1977

ER -

Applications of a planar separator theorem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this