Low-crossing spanning trees: an alternative proof and experiments
Panos Giannopoulos, Maximilian Konzack, Wolfgang Mulzer · Middlesex University Research Repository (Middlesex University Of London) · 2014
We give a quick proof that any planar n-point set has a spanning tree with crossing number O( √ n). Our proof relies on an LP-based approach by HarPeled [8], and it uses Farkas’ lemma. We also present a new heuristic for computing a spanning tree with low crossing number and compare it experimentally with other known approaches.