# 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.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.56-71, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_5〉
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01446264
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:50:56
Dernière modification le : jeudi 26 janvier 2017 - 09:35:11
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:55:59

### Fichier

##### Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

### Citation

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid. Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.56-71, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_5〉. 〈hal-01446264〉

### Métriques

Consultations de la notice