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), 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.
|Keywords||Geodesic graphs, Hamiltonian cycles, Non-crossing graphs, Perfect matchings, Spanning trees|
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