Emanation Graph: A Plane Geometric Spanner with Steiner Points

An emanation graph of grade $k$ on a set of points is a plane spanner made by shooting $2^{k+1}$ equally spaced rays from each point, where the shorter rays stop the longer ones upon collision. The collision points are the Steiner points of the spanner. Emanation graphs of grade one were studied by Mondal and Nachmanson in the context of network visualization. They proved that the spanning ratio of such a graph is bounded by $(2+\sqrt{2})\approx 3.41$. We improve this upper bound to $\sqrt{10} \approx 3.162$ and show this to be tight, i.e., there exist emanation graphs with spanning ratio $\sqrt{10}$. We also explore emanation graphs of grade two, which may have twice the number of edges compared to grade one graphs. We introduce a method of simplification that makes it an interesting geometric graph to be used for network visualization and geometric routing. In particular, we compare simplified emanation graphs against Shewchuk's constrained Delaunay triangulations on both synthetic and real-life datasets. Our experimental results reveal that the simplified emanation graphs outperform constrained Delaunay triangulations in common quality measures (e.g., edge count, angular resolution, average degree, total edge length) while maintain a comparable spanning ratio and Steiner point count.