Konfigurationen mit wenigen Kreuzungen

Sei G ein zusammenhängender Graph, der mit seiner Einbettung in die Ebene gegeben ist. Es ist bekannt, dass es NP-schwer ist zu entscheiden, ob G einen kreuzungsfreien Spannbaum besitzt. Wir zeigen, dass es sogar NP-schwer ist, die minimale Anzahl sich kreuzender Kanten in einem Spannbaum von G zu approximieren. Des weiteren zeigen wir, dass dieses Optimierungsproblem fest-Parameter-berechenbar ist. Schließlich geben wir ein gemischt-ganzzahliges Programm und eine einfache, aber effiziente und effektive Heuristik an, die häufig optimale Lösungen findet.

In Zusammenarbeit mit Andreas Spillner und Christian Knauer.

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 ]