Fixed-Parameter Algorithms for Finding Crossing-Free Spanning Trees in Geometric Graphs

Preprint series: 06-07, Reports on Computer Science

C. Knauer, A. Spillner

MSC:

Abstract: In this paper we consider the following problem.
We are given a geometric graph $$G$$ with $$n$$ vertices
and want to compute a crossing-free spanning tree
of $$G$$ or report that there is none.
We present fixed-parameter algorithms for
this problem. Based on a general approach
we outline how to achieve a running time
in $$O(2^{33 \sqrt{k} \log k} k^2 n^3 + n^3)$$.
Furthermore, we present another simple
algorithm running in $$O(2^{7.5k} k^2 n^3 + n^3)$$
time. The parameter $$k$$ is the number of
those vertices of $$G$$ that lie in the interior
of the convex hull of the vertex set of $$G$$.

Keywords: spanning tree, croosing-free, fixed-parameter algorithm