Configurations with few crossings in topological graphs

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 kappa-factors for kappa in {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-epsilon) for any epsilon > 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 mixed-integer linear program formulation for each problem and a simple but effective heuristic for spanning trees.