,
Configurations with Few Crossings in Topological Graphs
Proc. 16th Annu. Int. Symp. Algorithms Comput. (ISAAC'05), том 3827 из Lecture Notes in Computer Science, стр. 604--613. Springer-Verlag, (2005)
DOI: 10.1007/11602613_61
Аннотация
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.
