TY - JOUR
T1 - Applications of a planar separator theorem
AU - Lipton, Hichard J.
AU - Tarjan, Robert Endre
N1 - Funding Information:
This research partially supported by the U. S. PJnny Research Office, Grant No. DAAG 29-76-G-0338.
Funding Information:
This research partially supported by the U. S. Army Research Office, Grant No. DAAG 29-76-G-0338. This research partially supported by National Science Foundation grant MCS-75-22870 and by the Office of Naval Research contract N00014-76-C-0688.
Funding Information:
~**/ This research partially sUI-Jported by National Science Foundation grant IvICS-75-22870 al1d 1)y the Office of Naval Research contract N00014-76-c-0688.
Publisher Copyright:
© 1977 IEEE Computer Society. All rights reserved.
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 - http://www.scopus.com/inward/record.url?scp=85035070413&partnerID=8YFLogxK
UR - http://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 -