Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414541 | Computational Geometry | 2016 | 13 Pages |
Abstract
Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph , GP(S,E)GP(S,E), is a graph with vertex set S and edge set E such that each edge (a,b)∈E(a,b)∈E is the shortest geodesic path between a and b inside P . GPGP is said to be plane if the edges in E do not cross. If the points in S are colored, then GPGP is said to be properly colored provided that, for each edge (a,b)∈E(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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid,