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

by    C. Knauer, A. Spillner

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.