Advertisement
Published in:
2012 | OriginalPaper | Chapter
On Plane Constrained Bounded-Degree Spanners
Authors : Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
P
be a set of points in the plane and
S
a set of non-crossing line segments with endpoints in
P
. The visibility graph of
P
with respect to
S
, denoted
$\mathord{\it Vis}(P,S)$
, has vertex set
P
and an edge for each pair of vertices
u
,
v
in
P
for which no line segment of
S
properly intersects
uv
. We show that the constrained half-
θ
6
-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of
$\mathord{\it Vis}(P,S)$
. We then show how to construct a plane 6-spanner of
$\mathord{\it Vis}(P,S)$
with maximum degree 6 +
c
, where
c
is the maximum number of segments adjacent to a vertex.