Bounded Degree Planar Spanners
Darryl Hill

Much study has been done on planar spanning graphs of unbounded degree. However, there are many practical applications of graph theory that utilize spanners where having an arbitrarily high degree can be detrimental.

It is useful, therefore, to find spanning graphs that are of bounded degree. Since we are optimizing two attributes of the graph, what constitutes an optimal graph can be subjective. There are known planar spanners of extremely low degree, such as 4, but with an impractically high spanning ratio. The best spanning ratio, to the best of our knowledge, for a bounded degree planar graph is $(1+\theta/\cos(\theta/2)) \cdot 1.998$, where $\theta = 2\pi/14$ (approximately 2.92), but it is on a degree 14 graph, which in some scenarios might be too high. Recent work on bounded degree planar spanners has seen emphasis placed on optimizing both attributes, by giving graphs of degree 9 and 6 with a spanning ratio of 6. This can find uses in practical scenarios such as bluetooth networks, where we are limited by a maximum degree of 7.

We present a graph with a degree bound of 8 and a spanning ratio of $(1+\theta/\cos(\theta/2)) \cdot 1.998$, where $\theta = \pi/3$ (approximately 4.41). To the best of our knowledge, this is the lowest spanning ratio for any planar graph with maximum degree less than 14.