Planar Separators
Authors:
- Noga AlonNANoga Alon
- Paul SeymourPSPaul Seymour
- Robin ThomasRTRobin Thomas
- 1 May 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 7 (2) , 184-193
Abstract
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.
Keywords
This publication has 4 references indexed in Scilit:
- On the Problem of Partitioning Planar GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- Multicommodity flows in planar graphsJournal of Combinatorial Theory, Series B, 1981
- Decomposition of Km,n(Km,n∗) into cycles (circuits) of length 2kJournal of Combinatorial Theory, Series B, 1981
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979