Disk Packings and Planar Separators

Authors: Daniel A. Spielman and Shang-Hua Teng.

Bibliographic Information: Appeared in SCG 96: 12th Annual ACM Symposium on Computational Geometry, pages 349-358.


We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a $3/4$-separator of size $1.84\sqrt{n}$ in every $n$ node planar graph.
You can download the paper in postscript, compressed postscript, or PDF.

Here is a copy of the slides used in a presentation of the paper (note: these should be viewed in color)

Daniel A. Spielman
Last modified: Wed Aug 22 17:28:30 2001