**Preprint series:** 06-07, Reports on Computer Science

C. Knauer, A. Spillner

**MSC:**- 65D18 Computer graphics and computational geometry [See also 51N05, 68U05]

**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*

**Upload:** 2006-05-31

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.