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 geodesic 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
Keywords Geodesic graphs, Hamiltonian cycles, Non-crossing graphs, Perfect matchings, Spanning trees
Persistent URL dx.doi.org/10.1016/j.comgeo.2016.05.004
Journal Computational Geometry
Citation
Biniaz, A. (Ahmad), Bose, P, Maheshwari, A, & Smid, M. (2016). Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon. Computational Geometry, 57, 27–39. doi:10.1016/j.comgeo.2016.05.004