Approximating Spanning Trees with Low Crossing Numbers

Sariel Har-Peled.

We present a linear programming based algorithm for computing a
spanning tree T of a set P of n points in the
R^{d}, such that its crossing number is O(min( t
log n, n^{1-1/d})), where t the minimum crossing
number of any spanning tree of P. This is the first guaranteed
approximation algorithm for this problem. We provide a similar
approximation algorithm for the more general settings of building a
spanning tree for a set system with bounded VC dimension.

Our approach replaces the reweighting technique previously used in
computing such spanning trees.

Postscript,
PDF.
Last modified: Mon Jun 29 14:19:24 CDT 2009