SEPARATOR THEOREM FOR PLANAR GRAPHS.

Richard J. Lipton; Robert Endre Tarjan

doi:10.1137/0136016

SEPARATOR THEOREM FOR PLANAR GRAPHS.

Richard J. Lipton, Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

973 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	177-189
Number of pages	13
Journal	SIAM J Appl Math
Volume	36
Issue number	2
DOIs	https://doi.org/10.1137/0136016
State	Published - 1979

All Science Journal Classification (ASJC) codes

Applied Mathematics

Access to Document

10.1137/0136016

Cite this

@article{5ffa90c3488645c8b4fa5e92ee3e41db,

title = "SEPARATOR THEOREM FOR PLANAR GRAPHS.",

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

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

year = "1979",

doi = "10.1137/0136016",

language = "English (US)",

volume = "36",

pages = "177--189",

journal = "SIAM J Appl Math",

issn = "0036-1399",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - SEPARATOR THEOREM FOR PLANAR GRAPHS.

AU - Lipton, Richard J.

AU - Tarjan, Robert Endre

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

SN - 0036-1399

VL - 36

SP - 177

EP - 189

JO - SIAM J Appl Math

JF - SIAM J Appl Math

IS - 2

ER -

SEPARATOR THEOREM FOR PLANAR GRAPHS.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this