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 -