A Simple Proof of the Existence of a Planar Separator
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2011
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914073080233984 |
|---|---|
| author | Har-Peled, Sariel |
| author_facet | Har-Peled, Sariel |
| contents | We provide a simple proof of the existence of a planar separator by showing that it is an easy consequence of the circle packing theorem. We also reprove other results on separators, including:
(A) There is a simple cycle separator if the planar graph is triangulated. Furthermore, if each face has at most $d$ edges on its boundary, then there is a cycle separator of size O(sqrt{d n}).
(B) For a set of n balls in R^d, that are k-ply, there is a separator, in the intersection graph of the balls, of size O(k^{1/d}n^{1-1/d}).
(C) The k nearest neighbor graph of a set of n points in R^d contains a separator of size O(k^{1/d} n^{1-1/d}).
The new proofs are (arguably) significantly simpler than previous proofs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1105_0103 |
| institution | arXiv |
| publishDate | 2011 |
| record_format | arxiv |
| spellingShingle | A Simple Proof of the Existence of a Planar Separator Har-Peled, Sariel Computational Geometry We provide a simple proof of the existence of a planar separator by showing that it is an easy consequence of the circle packing theorem. We also reprove other results on separators, including: (A) There is a simple cycle separator if the planar graph is triangulated. Furthermore, if each face has at most $d$ edges on its boundary, then there is a cycle separator of size O(sqrt{d n}). (B) For a set of n balls in R^d, that are k-ply, there is a separator, in the intersection graph of the balls, of size O(k^{1/d}n^{1-1/d}). (C) The k nearest neighbor graph of a set of n points in R^d contains a separator of size O(k^{1/d} n^{1-1/d}). The new proofs are (arguably) significantly simpler than previous proofs. |
| title | A Simple Proof of the Existence of a Planar Separator |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/1105.0103 |