Configuratione with Few Crossings

Crossing-minimum spanning trees

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.

Publications

  1. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Configurations with few crossings in topological graphs. Technical Report 2005-24, Fakultät für Informatik, Universität Karlsruhe, September 2005. Available at http://digbib.ubka.uni-karlsruhe.de/volltexte/1000004122. [ bib | html | pdf ]
  2. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Configurations with few crossings in topological graphs. In Xiaotie Deng and Ding-Zhu Du, editors, Proc. 16th Annu. Internat. Symp. Algorithms Comput. (ISAAC'05), volume 3827 of Lecture Notes in Computer Science, pages 604-613. Springer-Verlag, 2005. [ bib | html | pdf | abstract ]
  3. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Spanning trees with few crossings in geometric and topological graphs. In Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 195-198, Eindhoven, 2005. [ bib | pdf ]