Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph, GP (S,E), is a graph with vertex set S and edge set E such that each edge (a, b) ∈ E is the shortest path between a and b inside P. GP is said to be plane if the edges in E do not cross. If the points in S are colored, then GP 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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-28678-5_5
Citation
Biniaz, A. (Ahmad), Bose, P, Maheshwari, A, & Smid, M. (2016). Plane geodesic spanning trees, hamiltonian cycles, and perfect matchings in a simple polygon. doi:10.1007/978-3-319-28678-5_5