  We design and engineer Fast-Sparse-Spanner, a simple and practical (fast and
memory-efficient) algorithm for constructing sparse low stretch-factor
geometric graphs on large pointsets in the plane. To our knowledge, this is the
first practical algorithm to construct fast low stretch-factor graphs on large
pointsets with average-degrees (hence, the number of edges) competitive with
that of greedy-spanners, the sparsest known class of Euclidean geometric
spanners.
  To evaluate our implementation in terms of computation speed, memory usage,
and quality of output, we performed extensive experiments with synthetic and
real-world pointsets, and by comparing it to our closest competitor Bucketing,
the fastest known greedy-spanner algorithm for pointsets in the plane, devised
by Alewijnse et al. (Algorithmica, 2017). We always found that
Fast-Sparse-Spanner generated near-greedy t-spanners while being fast and
memory-efficient. Our experiment with constructing a 1.1-spanner on a large
synthetic pointset with 128K points uniformly distributed within a square shows
more than a 41-fold speedup with roughly a third of the memory usage of that of
Bucketing, but with only a 3% increase in the average-degree of the resulting
graph. In terms of diameter, the graphs generated by Fast-Sparse-Spanner beat
greedy-spanners in most cases (have substantially lower diameter) while
maintaining near-greedy average-degree.
  As a byproduct of our research, we design and engineer Fast-Stretch-Factor, a
practical parallelizable algorithm that can measure the stretch-factor of any
graph generated by Fast-Sparse-Spanner. Our experiments show that it is much
faster than the naive Dijkstra-based stretch-factor measurement algorithm.
