%0 Conference Proceedings
%T Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
%+ Carleton University
%A Biniaz, Ahmad
%A Bose, Prosenjit
%A Maheshwari, Anil
%A Smid, Michiel
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Conference on Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammed Taghi Hajiaghayi
%Y Mohammad Reza Mousavi
%3 Topics in Theoretical Computer Science
%V LNCS-9541
%P 56-71
%8 2015-08-26
%D 2015
%R 10.1007/978-3-319-28678-5_5
%Z Computer Science [cs]Conference papers
%X Let <i>S</i> be a finite set of points in the interior of a simple polygon <i>P</i>. A <i>geodesic graph</i>, $G_P(S,E)$, is a graph with vertex set <i>S</i> and edge set <i>E</i> such that each edge $(a,b)\in E$ is the shortest path between a and b inside <i>P</i>. $G_P$ is said to be plane if the edges in <i>E</i> do not cross. If the points in <i>S</i> 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.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01446264/document
%2 https://inria.hal.science/hal-01446264/file/385217_1_En_5_Chapter.pdf
%L hal-01446264
%U https://inria.hal.science/hal-01446264
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9541
%~ IFIP-WG1-8
%~ IFIP-TTCS