A WSPD, Separator and Small Tree Cover for $𝒄$-Packed Graphs

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¹¹1A reviewer pointed us to the tree-like properties of the graph and the possibility of adapting the work by Chazelle [10]. 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 $\epsilon$, whereas previous constructions are not.

We summarise the main results of our paper. First, we show that any $c$-packed graph in ${ℝ}^d$ admits a well-separated pair decomposition (WSPD) of size $O((c^3/\epsilon )\cdot n)$, where $1/\epsilon$ is the separation constant of the WSPD. Note that we avoid the ${(1/\epsilon )}^d$ factor that appears in the sizes of many other WSPD constructions [7, 25]. Then, we show that any $c$-packed graph in ${ℝ}^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+\epsilon )$ distortion tree cover with $O(c^{2d+2}/{\epsilon }^d)$ trees. Our tree cover implies an approximate distance oracle (ADO) of size $O((c^{2d+2}/{\epsilon }^d)\cdot n)$ and $O(c^{2d+2}/{\epsilon }^d)$ query time. We summarise our results in Table 1.

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 [11], the mean curve [27], the shortcut Fréchet distance [13], subtrajectory clustering [5, 18] and the approximate nearest neighbour data structure [12]. However, $c$-packed graphs are less well understood [20, 21], 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 [13]. Low density graphs have been studied in map matching [11, 6]. The well-separated pair decomposition of [22] has size polynomial in $\lambda$ and $\epsilon$, but its disadvantage over those stated in Table 1 is that it has size $O(n\log n)$.

Well-Separated Pair Decompositions (WSPD) are used for compact representation of the quadratic distances between pairs of points in the metric. For metrics that allow for a sub-quadtratic size WSPD, they have therefore been used as fundamental tools to approximate solutions to a range of proximity problems that require looking at the distances between all pairs of points, such as nearest neighbour, diameter, stretch and minimum spanning tree. Not all metrics allow for a WSPD of subquadratic size, an example of which is the metric induced by a star tree with unit weight on all edges. For this metric, any WSPD requires a quadratic number of pairs. For a point set in ${ℝ}^d$, where $d$ is considered a constant, Callahan and Kosaraju [7] showed that there exists a WSPD with separation factor $\sigma$ of size $O({\sigma }^{d}n)$ that can be computed in $O(n\log n+{\sigma }^{d}n)$ time. In contrast to this, we show that for $c$-packed graphs, the size of the WSPD is not exponential in $d$, while maintaining that the size is linear. For graphs with bounded doubling dimension ($dim$), Har-Peled and Mendel [25] designed a $O(2^{O(dim)}n\log n+n{\epsilon }^{-O(dim)})$ expected time randomised algorithm to construct a WSPD of linear size with logarithmic query time. They also designed a deterministic construction which incurs a logarithmic dependency on the aspect ratio of the metric space. In the full version of this paper we show that a $c$-packed graph has doubling dimension $O(\log c)$. However, in contrast to previous results, our deterministic construction of the WSPD is, to the best of our knowledge, the first that does not depend on the aspect ratio of the metric space and does not incur any factors exponential in the dimension, assuming constant dimension.

Distance oracles are shortest path data structures for graphs. For planar graphs, Lipton and Tarjan [34, 35] proved the planar separator theorem, which states that any planar graph with $n$ vertices has a balanced separator of size $\sqrt{n}$. Using the separator to build a separator hierarchy, they constructed an exact distance oracle of size $O(n\sqrt{n})$. Thorup [39] and Klein [30] independently presented $(1+\epsilon )$-approximate distance oracles for planar graphs of size $O(n\log n)$, for any constant $\epsilon >0$. Subsequent works [28, 29, 41, 33] improved the preprocessing time, space, and query time. Dvořák and Norin [15] showed that if a graph admits a small size balanced separator, it also has small treewidth. Combined with our separator results this implies that $c$-packed graphs have treewidth $O(c)$. Chaudhuri and Zaroliagis[9] designed an exact distance oracle whose preprocessing time is single exponential in the treewidth of the graph. In contrast to these results, our algorithms do not incur any terms exponential in $c$.

Approximate distance oracles have been studied on non-planar graphs. Thorup and Zwick [40] constructed a $(2k-1)$-approximate distance oracle of $O(k{n}^{1+1/k})$ size on any general graph, and showed that the size bound is optimal under the Erdös girth conjecture. Gudmundsson, Levcopoulos, Narasimhan and Smid [19] provided a $(1+\epsilon )$-approximate distance oracle of size $O(n\log n)$ on any $t$-spanner, assuming $\epsilon ,t>0$ are constants. Gao and Zhang [16] constructed a $(1+\epsilon )$-approximate distance oracle of size $O(n\log n)$ for any unit-disk graph, assuming $\epsilon >0$ is a constant.

Balanced separators of sublinear size have been found for planar graphs [34], graphs of bounded genus [17], graphs that exclude a fixed minor [1], and graphs that are the 1-skeletons of simplicial complexes in 3-dimensions [36]. They have been used as a fundamental tool in devising efficient algorithms for graphs [1, 17, 35] and in numerical analysis [32, 36]. Randomized balanced separators can be found in expected linear time for $c$-packed graphs [26].

Metric embeddings approximate harder metric spaces by simpler, well-structured metric spaces, such as tree metrics. A tree cover for a finite metric space is a small number of trees such that the distance between any two points in the metric is preserved with low distortion in at least one of the trees. Tree covers with $(1+ϵ)$-distortion and a constant number of trees have been found for Euclidean metrics [2], doubling metrics [3] and planar metrics [8].

Split trees [7] or quadtrees [37] are commonly used in the construction of a geometric WSPD of a point set. An essential property of these is that the maximum Euclidean distance between two points contained in the same cell is always bounded by a function of the diameter of the cell. We construct a tree that fulfills a similar purpose to the trees above but for graph distances between points. We call this new type of tree a $\delta$-connected tree ($\delta$-CT). Each cell, corresponding to a cube $s$, of the $\delta$-connected tree is a $\delta$-connected set, meaning that points contained in the cell are within a graph distance of at most $\delta \cdot diam(s)$ from one another. To construct the $\delta$-CT, we use a bottom up approach. The leaves of the compressed quadtree are already $\delta$-connected sets. At higher levels of the compressed quadtree, we consider the $\delta$-connected sets of its children, and merge together pairs of previously $\delta$-connected sets that are also a $\delta$-connected set in the higher level. To obtain an efficient running time, we make two observations. First, when computing the $\delta$-connected sets for a higher level, it suffices to maintain a vertex representative for each $\delta$-connected set of the lower level. Second, to check if a pair of sets are $\delta$-connected, it suffices to check whether their representatives are path-connected in the cube centred at the cell but with double its radius.

To upper bound the graph diameter of the $\delta$-connected set in each cell of the $\delta$-CT we compute the length of intersection of edges with the cell and the $3^d$ surrounding cells in a canonical grid. To do this efficiently, we note that not all edges intersecting with a cell can contribute to a $\delta$-connected component inside the cell. We therefore construct a data structure that can be queried for the total length of all edges that can contribute to a $\delta$-connected component contained in a cell.

Combining these ideas obtains the following theorem. For details refer to Section 4.2.

We prove that every $c$-packed graph admits a balanced vertex separator of size $O(c)$. We start with the ring separator of Har-Peled and Mendel [25], which states that for a point set in ${ℝ}^d$, one can efficiently compute a pair of balls so that $n/2{\lambda }^3$ of the points are inside the inner ball, and $n/2{\lambda }^3$ of the points are outside the outer ball, where $\lambda$ is the doubling constant of ${ℝ}^d$. Using the ring separator, we construct a max-flow instance in a similar fashion to Gudmundsson et al. [20] to locate a cut of size $O(c)$. This cut $(1-1/2{\lambda }^3)$-separates the graph, in that it separates the graph into two components each with at most $n\cdot (1-1/2{\lambda }^3)$ points. We obtain the following theorem, for details refer to Section 5.

Our approach follows that of the celebrated “Dumbbell Theorem” [2] for Euclidean metrics. For $c$-packed graphs, we construct a linear number of dumbbells from the WSPD_G, which is constructed using the graph distances. The dumbbells are partitioned into groups, each of which satisfies the length-group property and the empty-region property with respect to the graph distance. The $c$-packedness property enables us to partition the dumbbells into a small number (depending only on the packedness value $c$ and the separation ratio $\sigma$ of WSPD_G) of groups, each of which satisfies the empty-region property. The main difficulty is proving the packing lemmas required for establishing the empty-region property. A dumbbell tree, which connects the dumbbells in a group hierarchically, is built for each group of dumbbells. The $c$-packedness property and the $c$-CT also enable us to do range searching and efficiently build the dumbbell trees. The dumbbell trees together constitute a tree cover for the $c$-packed metric. We obtain the following theorem. For details refer to the full version of the paper.

The tree cover of Theorem 5 immediately implies a $(1+\epsilon )$-approximate distance oracle for the $c$-packed metric.

Given a geometric graph $G(V,E)$ and cube $s$ in ${ℝ}^d$, we define the diameter of $s$ to be the length of a diagonal and denote it as $diam(s)$. We define the radius of $s$ to be half the diameter and denote it as $rad(s)$. We define $V(s)$ to be the subset of vertices of $V$ within $s$. We will need the following definitions.

Split trees [7] or quadtrees [37] are commonly used in the construction of a geometric WSPD of a point set. An essential property of these is that the Euclidean distance between two points contained in the same cell is always bounded by the diameter of the cell. In order to construct a WSPD_G we construct a new type of tree, which we will refer to as a $\delta$-connected tree ($\delta$-CT). This tree will satisfy the similar property, but relative to graph distances between the points in the graph, rather than their Euclidean distances. The main difference is that cells in a $\delta$-connected tree may overlap. We formally define this tree below.

Once we have a $\delta$-CT, it remains to upper bound the graph diameter of the $\delta$-connected set represented in each cell. With this upper bound, one can then follow a standard approach to compute a WSPD_G with separation factor $\sigma$ from the $\delta$-CT.

In Subsection 4.2.1 we show how to construct a $c$-CT, $T$, of a $c$-packed graph $G$. In Subsection 4.2.2 we then show how to upper bound the diameter of the $c$-connected set represented in each cell of $T$. In Subsection 4.2.4 we analyze the complexity of the construction.