TY - JOUR

T1 - Configurations with few crossings in topological graphs

AU - Knauer, C.

AU - Schramm, É.

AU - Spillner, A.

AU - Wolff, A.

PY - 2007

Y1 - 2007

N2 - 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-e for any e>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 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.

AB - 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-e for any e>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 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.

U2 - 10.1016/j.comgeo.2006.06.001

DO - 10.1016/j.comgeo.2006.06.001

M3 - Article

SN - 0925-7721

VL - 37

SP - 104

EP - 114

JO - Computational Geometry

JF - Computational Geometry

IS - 2

ER -