A WSPD, Separator and Small Tree Cover for c c -packed Graphs
Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, Sampson Wong · 2025
Read A WSPD, Separator and Small Tree Cover for c c -packed Graphs by Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, Sampson Wong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06884.txt.
Introduction
Lindsey Deryckere and four co-authors wrote a 2025 paper proving basic structural facts about a family of sparse geometric graphs. A graph is c-packed when its edges, in total length, stay controlled inside any ball. The property was proposed in 2010 but had been used mainly for curve distance problems. Wider algorithmic use was an open question.
The authors prove two foundations: these graphs admit a linear-size well-separated pair decomposition under their own distance metric, and they have constant-size balanced separators. From those, they build small tree covers for the shortest-path metric. Payoffs include a constant-size tree cover, an exact distance oracle of near-linear size, and an approximate one of linear size. The results widen the algorithmic territory where packedness helps. Distance queries on such networks become cheap.
Catalog record
| CREATOR | Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, Sampson Wong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06884
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A WSPD, Separator and Small Tree Cover for c c -packed Graphs Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, Sampson Wong Abstract The c c -packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in c c -packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the c c -packedness assumption, and more specifically, on c c -packed graphs. In this paper, we prove two fundamental properties of c c -packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size. School of Computer Science, The University of Sydney, [email protected] School of Computer Science, The University of Sydney, [email protected] School of Computer Science, The University of Sydney, [email protected] School of Computer Science, The University of Sydney, [email protected] Department of Computer Science, The University of Copenhagen, [email protected] ccs Theory of computation Computational geometry keywords Well-separated pair decomposition, separator, tree cover, distance oracles, realistic graphs † † runningauthor: L. Deryckere, J. Gudmundsson, A. van Renssen, Y. Sha and S. Wong † † copyright: Lindsey Deryckere, Joachim Gudmundsson, A. van Renssen, Y. Sha and S. Wong † † funding: This research was partially funded by the Australian Government through the Australian Research Council (project number DP240101353). 1 Introduction The study of graphs and their properties is a cornerstone of theoretical computer science. A wide variety of graph properties have been proposed in the literature, such as planarity [ 36 ] , treewidth [ 6 ] and doubling dimension [ 26 ] . By assuming these graph properties, one can often obtain better algorithmic or data structure solutions to graph theoretic problems. The c -packedness property [ 16 ] , proposed in 2010, is a geometric property that captures the spatial distribution of the edges in a graph. A graph is c -packed if, for any positive real r and any ball of radius r , the length of the edges contained in the ball is at most c\cdot r . Driemel, Har-Peled and Wenk [ 16 ] introduced the c -packedness property for polygonal curves, and showed that one can compute the Fréchet distance between a pair of c -packed curves in near-linear time. In 2013, Gudmundsson and Smid [ 24 ] adapted the c -packedness definition to graphs, and proposed a Fréchet distance data structure on c -packed trees with long edges that decides if there is a path in the tree with small Fréchet distance to a query curve. In 2023, Gudmundsson, Seybold and Wong [ 23 ] generalised the result of [ 24 ] by proposing a Fréchet distance data structure for all c -packed graphs. Despite the recent interest in c -packedness, its utility so far has been limited to Fréchet distance problems. Moreover, the fundamental properties of c -packed graphs are not well studied, thereby limiting the number of problems that can be solved efficiently on c -packed graphs. An open problem is whether c -packed graphs have applications beyond Fréchet distance problems. 1.1 Our Results We show that c -packed graphs lie in the intersection of two important graph classes, that is, doubling metrics and bounded treewidth graphs. Using the properties of doubling metrics and bounded treewidth graphs, one can obtain, for c -packed graphs, a linear-size well-separated pair decomposition, a linear-size exact distance oracle, a linear-size approximate distance oracle, and a constant-size tree cover. However, these constructions have processing times that are either (i) randomised, (ii) depend on the spread of the c -packed metric, or (iii) are exponential in the treewidth. See Table 1 , Column 3 1 1 1 A reviewer pointed us to the tree-like properties of the graph and the possibility of adapting the work by Chazelle [ 12 ] . However, such adaptations would be likely to incur an exponential dependency on c . . We provide the first deterministic constructions that are independent of the spread of the c -packed metric, for the aforementioned structures. Moreover, our preprocessing times and data structure sizes are polynomial in both c and \varepsilon , whereas previous constructions are not. We summarise the main results of our paper. First, we show that any c -packed graph in \mathbb{R}^{d} admits a well-separated pair decomposition (WSPD) of size O((c^{3}/\varepsilon)\cdot n) , where 1/\varepsilon is the separation constant of the WSPD. Note that we avoid the (1/\varepsilon)^{d} factor that appears in the sizes of many other WSPD constructions [ 9 , 28 ] . Then, we show that any c -packed graph in \mathbb{R}^{d} admits an O(c) -size separator. We use this separator to show that c -packed graphs have O(c) treewidth, and admits an exact distance oracle (EDO) of size O(cn\log n) . Finally, we combine our WSPD and the EDO to construct a (1+\varepsilon) distortion tree cover with O(c^{2d+2}/\varepsilon^{d}) trees. Our tree cover implies an approximate distance oracle (ADO) of size O((c^{2d+2}/\varepsilon^{d})\cdot n) and O(c^{2d+2}/\varepsilon^{d}) query time. We summarise our results in Table 1 . Previous New Preprocessing Size Source Preprocessing Size Source \multirow 2*WSPD \multirow 2* dd (1/\varepsilon)^{O(\log c)}\cdot n\log(\Delta n) \multirow 2* (1/\varepsilon)^{O(\log c)}\cdot n [ 41 ] \multirow 2* (c^{3}/\varepsilon)\cdot n\log n \multirow 2* (c^{3}/\varepsilon)\cdot n \multirow 2*Thm 3 Rand. (1/\varepsilon)^{O(\log c)}\cdot n\log n [ 28 ] EDO tw 2^{O(c^{3})}n c^{2}n [ 11 ] + [ 17 ] c^{2}n\log^{2}n cn\log n Thm 5 Tree cover dd (1/\varepsilon)^{O(\log c)}\cdot n\log^{2}(\Delta n) (1/\varepsilon)^{O(\log c)} [ 4 ] + [ 41 ] (c^{2d+6}/\varepsilon^{d+1})\cdot n\log n c^{2d+2}/\varepsilon^{d} Thm 6 ADO dd (1/\varepsilon)^{O(\log c)}\cdot n\log^{2}(\Delta n) (1/\varepsilon)^{O(\log c)}\cdot n [ 4 ] + [ 41 ] (c^{2d+6}/\varepsilon^{d+1})\cdot n\log n (c^{2d+2}/\varepsilon^{d})\cdot n Thm 7 Table 1: In the table, c = the c -packedness value, \varepsilon = either an \varepsilon^{-1} separation constant or a (1+\varepsilon) approximation ratio, Rand. = randomised algorithm, \Delta = spread of the doubling metric, d = dimension of the Euclidean space, dd = previous results using doubling dimension, tw = previous results using treewidth. 1.2 Related work The c -packedness property is a popular model for realistic curves. A wide range of Fréchet distance problems have been studied on c -packed curves, including map matching [ 13 ] , the mean curve [ 30 ] , the shortcut Fréchet distance [ 15 ] , subtrajectory clustering [ 7 , 21 ] and the approximate nearest neighbour data structure [ 14 ] . However, c -packed graphs are less well understood [ 23 , 24 ] , despite often being used as a vital stepping stone towards a related property called \lambda -low density, which was also introduced by Driemel and Har-Peled [ 15 ] . Low density graphs have been studied in map matching [ 13 , 8 ] . The well-separated pair decomposition of [