language: en

Disk Packings and Planar Separators

Daniel A. Spielman
U.C. Berkeley/MIT
Shang-Hua Teng
University of Minnesota

Abstract We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a 3=4-separator of size 1:84 p n for every n node planar graph. Our bound is derived from an analysis of disk packings on the sphere.

1. Introduction