Configurations with few crossings in topological graphs (Q876504)

A topological graph is an undirected graph \(G=(V, E)\) embedded in the Euclidean plane such that any two edges intersect in at most a finite number of points. The paper investigates the existence of special configurations, namely spanning trees, \(s\)-\(t \) paths, cycles, matchings and \(k\)-factors for \(k \in \{1, 2\}\), for which the number of crossings is minimal. The paper also provides a fixed-parameter algorithm that tests in \(O^*(2^k)\) time whether \(G\) has a crossing-free configuration in the above cases. The fixed-parameter constant \(2^k\) is improved to \((\sqrt 3)^k\) for \(s\)-\(t\) paths and cycles, while minor improvements are provided in the other cases. Also, each \(O^*(\beta ^k)\)-time decision algorithm can be turned into a \(O^*((\beta + 1)^k)\)-time optimization algorithm that computes a configuration with the minimum number of crossings.