PLANAR SEPARATORS

被引：54

作者：

ALON, N

SEYMOUR, P

THOMAS, R

机构：

[1] BELLCORE,MORRISTOWN,NJ 07962

[2] RUTGERS STATE UNIV,CTR DISCRETE MATH & THEORET COMP SCI,NEW BRUNSWICK,NJ 08903

[3] GEORGIA INST TECHNOL,GRAD INST TECHNOL,ATLANTA,GA 30332

[4] GEORGIA INST TECHNOL,SCH MATH,ATLANTA,GA 30332

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 02期

关键词：

SEPARATORS; K-SHIELDS; CORNER;

D O I：

10.1137/S0895480191198768

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The authors give a short proof of a theorem of Lipton and Tarjan, that, for every planar graph with n > 0 vertices, there is a partition (A, B, C) of its vertex set such that \A\, \B\ < 2/3n, \C\ less-than-or-equal-to 2(2n)1/2, and no vertex in A is adjacent to any vertex in B. Secondly, they apply the same technique more carefully to deduce that, in fact, such a partition (A, B, C) exists with \A\, \B\ < 2/3n, and \C\ less-than-or-equal-to 3/2(2n)1/2; this improves the best previously known result. An analogous result holds when the vertices or edges are weighted.

引用

页码：184 / 193

页数：10