##
On Spanning Trees with Low Crossing Numbers

###
Emo Welzl
Institut für Informatik
Freie Universität Berlin
Report B 92-02
January 1992

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-02.ps.gz

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.