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
Planar Separators
Noga Alon, Paul Seymour, Robin Thomas · SIAM Journal on Discrete Mathematics · 1 May 1994
Abstract
The full text is at the publisher
You can read the abstract here, or open it 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
- NobleID
- NI6P35W50R74S54
Discussion
Citations
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