Disk packings and planar separators
Daniel A. Spielman, Shang‐Hua Teng · 1996
We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a 3/4-separator of size 1.84+ for every n node planar graph.Our bound is derived from an analysis of disk packings on the sphere,