Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph, G P ( S , E ) , is a graph with vertex set S and edge set E such that each edge ( a , b ) ź E is the shortest geodesic path between a and b inside P. G P is said to be plane if the edges in E do not cross. If the points in S are colored, then G P is said to be properly colored provided that, for each edge ( 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.
['Ahmad Biniaz', 'Prosenjit Bose', 'Anil Maheshwari', 'Michiel H. M. Smid']
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon