Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
Abstract
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.
Domains
Origin | Files produced by the author(s) |
---|