Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points
share
Emanation graphs of grade k, introduced by Hamedmohseni, Rahmati, and Mondal, are plane spanners made by shooting 2^k+1 rays from each given point, where the shorter rays stop the longer ones upon collision. The collision points are the Steiner points of the spanner. We introduce a method of simplification for emanation graphs of grade k=2, which makes it a competent spanner for many possible use cases such as network visualization and geometric routing. In particular, the simplification reduces the number of Steiner points by half and also significantly decreases the total number of edges, without increasing the spanning ratio. Exact methods of simplification along with mathematical proofs on properties of the simplified graph is provided. 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.
READ FULL TEXT