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.
%0 Conference Paper
%1 kssw-cfctg-05
%A Knauer, Christian
%A Schramm, Étienne
%A Spillner, Andreas
%A Wolff, Alexander
%B Proc. 16th Annu. Int. Symp.
Algorithms Comput. (ISAAC'05)
%D 2005
%E Deng, Xiaotie
%E Du, Ding-Zhu
%I Springer-Verlag
%K myown
%P 604--613
%R 10.1007/11602613_61
%T Configurations with Few Crossings in Topological
Graphs
%V 3827
%X 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.
@inproceedings{kssw-cfctg-05,
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 $\kappa \in \{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
\(\varepsilon > 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.},
added-at = {2024-04-29T21:12:31.000+0200},
author = {Knauer, Christian and Schramm, Étienne and Spillner, Andreas and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2bedfd4695822674d2f12143fc87ca5ee/awolff},
booktitle = {Proc. 16th Annu. Int. Symp.
Algorithms Comput. (ISAAC'05)},
conflocation = {Sanya, Hainan, China},
confmonth = {{19--21~}#dec},
doi = {10.1007/11602613_61},
editor = {Deng, Xiaotie and Du, Ding-Zhu},
interhash = {f6e10ea5cab0fff43fc9b4598b79f67b},
intrahash = {bedfd4695822674d2f12143fc87ca5ee},
keywords = {myown},
pages = {604--613},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/kssw-cfctg-05.pdf},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/kssw-cfctg-05-slides.pdf},
succeeds = {kssw-stfcg-05},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Configurations with Few Crossings in Topological
Graphs},
volume = 3827,
year = 2005
}