Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon

Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph  , GP(S,E)GP(S,E), is a graph with vertex set S and edge set E   such that each edge (a,b)∈E(a,b)∈E is the shortest geodesic path between a and b inside P  . GPGP is said to be plane if the edges in E do not cross. If the points in S   are colored, then GPGP is said to be properly colored   provided that, for each edge (a,b)∈E(a,b)∈E, a and b have different colors. In this paper we consider the problem of computing (properly colored) plane geodesic perfect matchings, Hamiltonian cycles, and spanning trees of maximum degree three.