Home Bookmarks Papers Blog

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 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.

Postscript, PDF.

Last modified: Mon Jun 29 14:19:24 CDT 2009