Abstract
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 show that the problems are
fixed-parameter tractable if we use the number of
crossings in the given graph as the
parameter. Finally we present a simple but effective
heuristic for spanning trees.
Users
Please
log in to take part in the discussion (add own reviews or comments).