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(2k) 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(1.9999992k) for spanning trees and O((3)k) for s-t paths and cycles. For spanning trees we also have an O(1.968k)-time Monte-Carlo algorithm. Each O(βk)-time decision algorithm can be turned into an O((β+1)k)-time optimization algorithm that computes a configuration with the minimum number of crossings.