More Like this

1. Hamiltonicity of sparse pseudorandom graphs

   https://doi.org/10.1017/S0963548325000070  

   Ferber, Asaf; Han, Jie; Mao, Dingjia; Vershynin, Roman (July 2025, Combinatorics, Probability and Computing)
2. Efficiently Constructing Sparse Navigable Graphs

   Conway, Alex; Dhulipala, Laxman; Farach-Colton, Martin; Johnson, Rob; Landrum, Ben; Musco, Christopher; Shechter, Yarin; Suel, Torsten; Wen, Richard (January 2026, ACM-SIAM Symposium on Discrete Algorithms (SODA).)
3. Incremental SCC Maintenance in Sparse Graphs

   https://doi.org/10.4230/LIPIcs.ESA.2021.14  

   Bernstein, Aaron; Dudeja, Aditi; Pettie, Seth (January 2021, 29th Annual European Symposium on Algorithms (ESA 2021))
4. Private Graphon Estimation for Sparse Graphs

   Borgs, Christian; Chayes, Jennifer; Smith, Adam (January 2015, Advances in neural information processing systems)
5. Local Algorithms for Sparse Spanning Graphs

   https://doi.org/10.1007/s00453-019-00612-6  

   Levi, Reut; Ron, Dana; Rubinfeld, Ronitt (January 2020, Algorithmica)

   Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ϵ)n edges (where n is the number of vertices and ϵ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be Ω(n−−√). This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is poly(1/ϵ,h) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences. 

   more » « less