Approximating Spanning Trees with Low Crossing Numbers
We present a linear programming based algorithm for computing a
spanning tree T of a set P of n points in the
Rd, such that its crossing number is O(min( t
log n, n1-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.