On the edge crossings of the greedy spanner.
D. Eppstein and
H. Khodabandeh.
arXiv:2002.05854.
Proc. 37th International Symposium on Computational Geometry (SoCG 2021).
Leibniz International
Proceedings in Informatics (LIPIcs) 189, 2021, pp. 33:1–33:17, doi:10.4230/LIPIcs.SoCG.2021.33.
Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.