2011/04/30 by Sariel Har-Peled, Har-Peled, Sariel · 1 voice
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1105.0103
openalex publication_date 2011/04/30 · arxiv published 2011/04/30 · arxiv updated 2025/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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(sqrtd n). (B) For a set of n balls in Rd, that are k-ply, there is a separator, in the intersection graph of the balls, of size O(k1/dn1-1/d). (C) The k nearest neighbor graph of a set of n points in Rd contains a separator of size O(k1/d n1-1/d). The new proofs are (arguably) significantly simpler than previous proofs.