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.

On Spanning Trees with Low Crossing Numbers

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