Configuratione with Few Crossings

Given a connected graph G with its embedding in the plane, does G contain a crossing-free spanning tree? This problem is known to be NP-complete. We show that the problem of finding a spanning tree with the minimum number of edge crossings is even NP-hard to approximate. We further show that this optimization problem is fixed-parameter tractable. We also give a mixed-integer formulation and a simple, but efficient and effective heuristic that often finds optimal solutions.

Joint work with Andreas Spillner and Christian Knauer.