I view this work as falling withing the paradigm of local computation algorithms (LCAs). Recall that these algorithms are given access to an input oracle and emulate access to an output oracle, which may represent some substructure of the input, while making as few (i.e., sublinear) queries to the input oracle per each request to the output oracle. Typically, these algorithms are required to be history dependent (wrt prior requests to the output oracle), but the same randomness may be used in all invocations. Viewed from that perspective, the current study prposes to move some of the emulation work to a preprocessing stage so that all on-line requests can be served much faster. (In the current model, one may distinguish between algorithms that acccess only the data structure created at the preprocessed stage from algorithms that may also access the input oracle at the emulation stage.)
The main observation that pivots the new algorithms is that the high complexity of determining a sparse spanning subgraph is due to ``relatively dense'' subgraphs of the original graph, where a subgraph is called relatively dense if it has far more edges than vertices. However, finding spanning subgraphs of relatively dense graphs is relatively easy. Hence, the idea is to identify such subgraphs, use sparse spanning subgraphs for them, and use all edges that have endpoints in different subgraphs. (The foregoing description as well as the following pragraph refer to sparse spanning subgraphs; obtaining k-spanners requires a different structure.)
Needless to say, the above description is over-simplified. Actually, one iteratively groups vertices while maintaining a spanning tree in each group. The process proceeds in epochs such that in the $i$th epoch one deals with groups of approximate size $2^i$. Letting $n$ denote the nunber of vertices in the graph, in each epoch one selects at random $tildeO(n)$ edges with an endpoint in some group of the corresponding size. Edges to groups of similar or larger size are added to the spanning forest, causing the merging of the corresponding groups. Loosely speaking, the point is that, in epoch $i$, if a group of size $2^i$ has $Omega(2^i)$ edges going to groups of size at least $2^i$, then it will be merged to one of these groups, forming a group of size at least $2^{i+1}$ (for the next epoch). Hence, with high probability, at the end of the epoch, the number of edges between unmerged groups of size $2^i$ and groups of size at least $2^i$ is at most $o(n)$. The final subgraph will consist of the trees that span each of the resulting groups along with all edges between the different groups.
Comments: The algorithms work in a model that allows for querying the input oracle also in the output emulation stabge. Alternatively, they may only serve requests (i.e., membership in the sparse subgraph) regarding the original edges. The tildeO(1) notion in the abstract hides factors that are poly-logarithmic in the number of vertices.
Suppose we wish to compute a sparse spanning subgraph H of a given n-node, m-edge input graph G. This can be achieved in O(m+n) time via a single breadth-first search. A natural question is whether this runtime can be improved to sublinear for some range of parameters, say O(n^{1.9}) time, which would be sublinear for large m. A simple lower bound construction shows that this is not possible; Omega(m + n) time is necessary.
However, we observe that these lower bounds only hold when we are required to output H as an adjacency list. Consider instead representing H as an adjacency oracle - a data structure that can be queried with an edge from G that returns a bit saying whether the edge is in H in tildeO(1) time (think akin to an adjacency matrix). We show that adjacency oracles of size tildeO(n) spanning subgraphs can be computed in tildeO(n) time, also proving that Omega(n) time is necessary.
If we wish to preserve approximate distances and not just connectivity, we give algorithms that compute adjacency oracles of size tildeO(n^{3/2}) multiplicative 3-spanners and size tildeO(n^{4/3}) multiplicative 5-spanners, each in tildeO(n^{3/2}) time. Assuming the Erdos Girth Conjecture, these spanners are near-optimal size.