@inproceedings{d3c3ecd52cf847cf858c14ff361de48d,

title = "Configurations with few crossings in topological graphs",

abstract = "In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, s–t paths, cycles, matchings, and ¿-factors for ¿ ¿ {1,2}. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k 1¿-¿e for any e > 0, where k is the number of crossings in G. We then show that the problems are fixed-parameter tractable if we use the number of crossings in the given graph as the parameter. Finally we present a simple but effective heuristic for spanning trees.",

author = "C. Knauer and {\'E}. Schramm and A. Spillner and A. Wolff",

year = "2005",

doi = "10.1007/11602613_61",

language = "English",

isbn = "3-540-30935-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "604--613",

editor = "X. Deng and D.Z. Du",

booktitle = "Algorithms and computation : 16th international symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings",

address = "Germany",

}