TY - JOUR
T1 - SEPARATOR THEOREM FOR PLANAR GRAPHS.
AU - Lipton, Richard J.
AU - Tarjan, Robert Endre
N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 1979
Y1 - 1979
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0018457301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0018457301&partnerID=8YFLogxK
U2 - 10.1137/0136016
DO - 10.1137/0136016
M3 - Article
AN - SCOPUS:0018457301
VL - 36
SP - 177
EP - 189
JO - SIAM Journal on Applied Mathematics
JF - SIAM Journal on Applied Mathematics
SN - 0036-1399
IS - 2
ER -