We study the problem of computing a spanning tree in a connected topological graph such that the number of crossings in the spanning tree is minimum. We show it is NP-hard to find a good approximation of the minimum number of crossings even in geometric graphs. On the other hand we show that the problem is fixed-parameter tractable and present a mixed integer linear program formulation.
|Title of host publication||Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)|
|Editors||M.T. Berg, de|
|Publisher||Technische Universiteit Eindhoven|
|Publication status||Published - 2005|