On Plane Constrained Bounded-Degree Spanners

Let P be a finite 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 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...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2019-04, Vol.81 (4), p.1392-1415
Main Authors: Bose, Prosenjit, Fagerberg, Rolf, van Renssen, André, Verdonschot, Sander
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Apexes
Computer Science
Computer Systems Organization and Communication Networks
Construction planning
Data Structures and Information Theory
Graph theory
Mathematics of Computing
Segments
Theory of Computation
Visibility
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let P be a finite 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 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 Vis ( P , S ) . We then show how to construct a plane 6-spanner of Vis ( P , S ) with maximum degree 6 + c , where c is the maximum number of segments of S incident to a vertex.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-018-0476-8