On Spanning Trees with Low Crossing Numbers
Institut für Informatik
Freie Universität Berlin
Report B 92-02
Get the report here or by anonymous ftp:
Every set S of n points in the plane has a spanning tree such that no line disjoint from S has more than $0 (\sqrt n)$ intersections with the tree (where the edges are embedded as straight line segments). We review the proof of this result (originally proved by Bernard Chazelle and the author in a more general setting), point at some methods for constructing such a tree, and describe some algorithmic and combinatorial applications.