Skip to Main content Skip to Navigation
Conference papers

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, $G_P(S,E)$, is a graph with vertex set S and edge set E such that each edge $(a,b)\in E$ is the shortest 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)\in 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01446264
Contributor : Hal Ifip <>
Submitted on : Wednesday, January 25, 2017 - 4:50:56 PM
Last modification on : Thursday, January 26, 2017 - 9:35:11 AM
Document(s) archivé(s) le : Wednesday, April 26, 2017 - 3:55:59 PM

File

385217_1_En_5_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid. Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.56-71, ⟨10.1007/978-3-319-28678-5_5⟩. ⟨hal-01446264⟩

Share

Metrics

Record views

102

Files downloads

192