Configurations with Few Crossings in Topological Graphs

, , , and . Proc. 16th Annu. Int. Symp. Algorithms Comput. (ISAAC'05), volume 3827 of Lecture Notes in Computer Science, page 604--613. Springer-Verlag, (2005)


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 ın \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.

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication