On plane bounded-degree spanners

André van Renssen

Let P be a set of points in the plane. It has previously been shown that the half-Θ6-graph (which is identical to the Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of the complete graph on P. This graph, however, can have high degree. Bonichon et al. show how to construct a plane 6-spanner with maximum degree 6 [ICALP 2010]. In this talk, we simplify the construction method of this bounded-degree spanner and the proofs associated with it.