Zusammenfassung
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 $\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-\varepsilon$ for any $>
0$, where $k$ is the number of crossings in
$G$. We then give a simple fixed-parameter
algorithm that tests in $O^\star(2^k)$ time whether
$G$ has a non-crossing configuration for any of the
above, where the $O^\star$-notation neglects
polynomial terms. For some configurations we have
faster algorithms. The respective running times are
$O^\star(1.9999992^k)$ for spanning trees and
$O^\star((3)^k)$ for $s$-$t$ paths and
cycles. For spanning trees we also have an
$O^\star(1.968^k)$-time Monte-Carlo algorithm. Each
$O^\star(\beta^k)$-time decision algorithms can be
turned into an $O^\star((\beta+1)^k)$-time
optimization algorithm that computes a configuration
with the minimum number of crossings.
Nutzer