%0 Journal Article %1 kssw-cfctg-07 %A Knauer, Christian %A Schramm, Étienne %A Spillner, Andreas %A Wolff, Alexander %D 2007 %J Computational Geometry: Theory and Applications %K %N 2 %P 104--114 %R 10.1016/j.comgeo.2006.06.001 %T Configurations with Few Crossings in Topological Graphs %V 37 %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 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.

@article{kssw-cfctg-07, 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$. \par 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((\sqrt{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.}, added-at = {2023-12-12T20:56:14.000+0100}, author = {Knauer, Christian and Schramm, {\'E}tienne and Spillner, Andreas and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2f06dda3108e31daef0eaea6ef0d7a3fd/admin}, cites = {df-pc-99, gb-agefc-05, h-a-04, jw-cdccp-93, kln-nstl-91, kssw-cfctg-05, kssw-cfctg-05t, mv-osvea-80, rw-rsols-93, t-spftf-54, ZZZ}, doi = {10.1016/j.comgeo.2006.06.001}, interhash = {369e4913a348fbe6425511c1430a8c70}, intrahash = {f06dda3108e31daef0eaea6ef0d7a3fd}, jourmonth = {jul}, journal = {Computational Geometry: Theory and Applications}, keywords = {}, number = 2, pages = {104--114}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/kssw-cfctg-07.pdf}, succeeds = {kssw-cfctg-05t}, timestamp = {2023-12-12T20:56:14.000+0100}, title = {Configurations with Few Crossings in Topological Graphs}, volume = 37, year = 2007 }