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 κ-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 k1−ε for any ε>0, where k is the number of crossings in G.We then give a simple fixed-parameter algorithm that tests in O⋆(k2) time whether G has a crossing-free configuration for any of the above, where the O⋆-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are O⋆(k1.9999992) for spanning trees and for s-t paths and cycles. For spanning trees we also have an O⋆(k1.968)-time Monte-Carlo algorithm. Each O⋆(βk)-time decision algorithm can be turned into an O⋆(k(β+1))-time optimization algorithm that computes a configuration with the minimum number of crossings.