NobleBlocks

From the research index

The paper comes from the research index. It wasn’t submitted here.

Journal article

Planar Separators

Noga Alon, Paul Seymour, Robin Thomas

SIAM Journal on Discrete Mathematics1 May 1994

Abstract

No PDF here

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

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| < \frac{2}{3}n,|C| \leq 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| < \frac{2}{3}n$, and $|C| \leq \frac{3}{2}( 2n )^{1/2} $ ; this improves the best previously known result. An analogous result holds when the vertices or edges are weighted.

Identifiers

Discussion

Citations

99Cited by
5References

Topics

Details

Published
1 May 1994
Publisher
Society for Industrial and Applied Mathematics
Issue
Volume 7 · Issue 2 · Pages 184–193
ISSN
0895-4801
Language
EN

More

Suggest a correction or report