There are Plane Spanners of Maximum Degree 4

Nicolas Bonichon, Iyad A. Kanj, Ljubomir Perković, Ge Xia · 2014

Let ϵ be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t ≥ 1, a spanning subgraph G of ϵ is said to be a t-spanner, or simply a spanner, if for any pair of vertices u, v in ϵ the distance between u and v in G is at most t times their distance in ϵ. A spanner is plane if its edges do not cross.

Read the paper · More papers on PaperTik