Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points

Bardia Hamedmohseni, Zahed Rahmati, Debajyoti Mondal


Abstract
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.
Cite:
Bardia Hamedmohseni, Zahed Rahmati, and Debajyoti Mondal. 2020. Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points. SOFSEM 2020: Theory and Practice of Computer Science:607–616.
Copy Citation: