Authors:
Daniel A. Spielman
and Shang-Hua Teng.
Bibliographic Information:
Appeared in
SCG 96: 12th Annual ACM Symposium on Computational Geometry,
pages 349-358.
Abstract:
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