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 (Formula presented.), 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-(Formula presented.)-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of (Formula presented.). We then show how to construct a plane 6-spanner of (Formula presented.) with maximum degree (Formula presented.), where c is the maximum number of segments of S incident to a vertex.

, , ,
School of Computer Science

Bose, P, Fagerberg, R. (Rolf), van Renssen, A. (André), & Verdonschot, S. (Sander). (2018). On Plane Constrained Bounded-Degree Spanners. Algorithmica, 1–24. doi:10.1007/s00453-018-0476-8