There are different measures which can be used to analyze the quality of a spanner. The most common measures are edge count, total weight and maximum vertex degree. Asymptotically optimal values for these measures are edges, weight and maximum degree (here MST denotes the weight of the minimum spanning tree).
Finding a spanner in the Euclidean plane with minimal dilation over n points with at most m edges is known to be NP-hard.[3]
Many spanner algorithms exist which excel in different quality measures. Fast algorithms include the WSPD spanner and the Theta graph which both construct spanners with a linear number of edges in time. If better weight and vertex degree is required the Greedy spanner can be computed in near quadratic time.
The greedy spanner or greedy graph is defined as the graph resulting from repeatedly adding an edge between the closest pair of points without a t-path. Algorithms which compute this graph are referred to as greedy spanner algorithms. From the construction it trivially follows that the greedy graph is a t-spanner.
The greedy spanner was first described in the PhD thesis of Gautam Das[4] and conference paper[5] and subsequent journal paper by Ingo Althöfer et al[6]. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.
The greedy spanner achieves asymptotically optimal edge count, total weight and maximum vertex degree and also performs best on these measures in practice.
It can be constructed in time using space.[7]
Chew's main result was that for a set of points in the plane there is a triangulation of this pointset such that for any two points there is a path along the edges of the triangulation with length at most the Euclidean distance between the two points. The result was applied in motion planning for finding reasonable approximations of shortest paths among obstacles.
The best upper bound known for the Euclidean Delaunay triangulation is that it is a -spanner for its vertices.[8]
The lower bound has been increased from to just over that, to 1.5846
.[9]
Chew, L. Paul (1986), "There is a planar graph almost as good as the complete graph", Proc. 2nd Annual Symposium on Computational Geometry, pp. 169–177, doi:10.1145/10515.10534, S2CID 42010166. Klein, Rolf; Kutz, Martin (2007), "Computing geometric minimum-dilation graphs is NP-hard", in Kaufmann, Michael; Wagner, Dorothea (eds.), Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006, Lecture Notes in Computer Science, vol. 4372, Springer Verlag, pp. 196–207, doi:10.1007/978-3-540-70904-6, ISBN 978-3-540-70903-9. Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah (1990), "Generating sparse spanners for weighted graphs", SWAT 90, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 26–37, CiteSeerX 10.1.1.158.2241, doi:10.1007/3-540-52846-6_75, ISBN 978-3-540-52846-3, retrieved March 16, 2021 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry, 9 (1): 81–100, doi:10.1007/BF02189308, MR 1184695 Bose, P.; Carmi, P.; Farshi, M.; Maheshwari, A.; Smid, M. (2010), "Computing the greedy spanner in near-quadratic time.", Algorithmica, 58 (3): 711–729, doi:10.1007/s00453-009-9293-4, S2CID 8068690