### Towards plane spanners of degree 3

#### Abstract

Let $S$ be a finite set of points in the plane. In this paper we consider the problem of computing plane spanners of degree at most three for $S$.

- If $S$ is in convex position, then we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner for $S$ whose vertex degree is at most 3.
- If $S$ is the vertex set of a non-uniform rectangular lattice, then we present an algorithm that constructs a plane $3\sqrt{2}$-spanner for $S$ whose vertex degree is at most 3.
- If $S$ is in general position, then we show how to compute plane degree-3 spanners for $S$ with a linear number of Steiner points.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v8i1a2

ISSN: 1920-180X