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, G(P)(S, E), is a graph with vertex set S and edge set E such that each edge (a, b) is an element of 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) is an element of 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. (C) 2016 Elsevier B.V. All rights reserved.