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.
  • @awolff
  • @fink
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).