Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes

Our main technical contribution is to compute a recursive division in linear time, for any Euclidean graph class that satisfies the following criteria:

1. (I)

   The graph $G$ admits a sublinear separator that can be computed in linear time.

2. (II)

   The combinatorially contracted graphs $G_i$ of $G$ (refer to Definition 8) are sparse, i.e., any $\overline{k}$-vertex subgraph of $G_i$ is sparse.

3. (III)

   A closed surface in ${ℝ}^d$ (such as a Jordan curve in ${ℝ}^2$, a sphere in ${ℝ}^d$) is used to find the separator in (I). The closed surface cuts a sublinear number of geometrical objects (such as segments, balls) associated with the vertices in $G$, and these associated vertices form the separator. Moreover, a random closed surface cuts a sublinear number of geometrical objects associated with the vertices in $G$ in expectation.

4. (IV)

   The graph class of $G$ is subgraph-closed.

Compared with HKRS [12], criteria (II)-(IV) replace the minor-closed condition, and can be satisfied by a family of non-minor-closed graph classes. Criteria (I)-(IV) are formally stated in Section 3, in which we use criteria (I)-(IV) to compute a recursive division of the Euclidean graph class in linear time. Once we have the recursive division¹¹1To be precise, the recursive division should satisfy the conditions in Inequalities (1)., we can apply HKRS’s edge-relaxation algorithm on it to compute SSSP in linear time.

In particular, we show that $\tau$-lanky graphs, the intersection graphs of $k$-ply neighborhood systems and the intersection graphs of $\kappa$-thick cubical neighborhood systems all satisfy the above criteria. Thus we can compute a recursive division (and SSSP) for these Euclidean graph classes in linear time. In this way, we answer Open Problems 2, 3 and 4 affirmatively.

Our approach to constructing a recursive division in linear time uses contracted graphs of the Euclidean graph classes. The main technical challenges of using contracted graphs for Euclidean graph classes are:

• $\mathrm{■}$

  Edge contraction for planar or minor-closed graphs is a combinatorial operation. The contracted graphs in HKRS [12] are obtained by such combinatorial edge contractions. In HKRS’s approach, the resulting contracted graphs must remain in the original graph class to guarantee that they have sublinear separators. This is not the case for Euclidean graph classes.

• $\mathrm{■}$

  In Euclidean graph classes, vertices are points in ${ℝ}^d$ and edges are segments in ${ℝ}^d$. Unfortunately, edge contraction in the Euclidean space does not preserve geometric properties and seems meaningless. For example, if an edge $(a,b)\in {ℝ}^d$ is contracted into a new vertex $c\in {ℝ}^d$, any edge $e_a$ or $e_b$ attached to $a$ or $b$ would now be attached to $c$. There is no way to choose $c$ so that the geometric properties of $e_a$ and $e_b$ (e.g. length, intersections) are preserved.

Although edge contractions in the Euclidean space are incompatible with the geometric properties of straight line embeddings, we overcome this obstacle by performing edge contractions combinatorially and proving that 1) the combinatorially contracted graphs admit sublinear balanced separators, and 2) such balanced separators can be computed in time linear to the size of the contracted graph. These properties are unknown before and we believe that they are of independent interest.

A recursive division of a graph divides the graph into regions, then divides the regions into subregions, and so on recursively. There are two approaches to computing a recursive division of planar graph in linear time. The first approach is to adapt Goodrich’s [9] recursive separator decomposition algorithm to compute a recursive division of the planar graph in linear time. Goodrich’s recursive separator decomposition algorithm emulates Lipton and Tarjan’s planar separator algorithm, maintains tree structures used in LT’s algorithm and other tree structures dynamically for the divided pieces during decomposition. In this way a separator of the divided piece can be computed in time sublinear to the size of the piece. The second approach, attributed to Frederickson [7] and HKRS [12], is to contract the graph consecutively into a sequence of contracted graphs, then in reverse order divide and expand the contracted graphs to get a recursive division. The first approach relies on specific properties of planar graphs and maintaining spanning trees dynamically. It seems infeasible to use similar ideas on many other graph classes. The second approach relies on edge contraction and the minor-closed property of planar graphs. However, Euclidean graph classes are not minor-closed, yet edge contraction in the Euclidean space seems meaningless.

We compute a recursive division of the Euclidean graph classes by (1) performing edge contractions on the Euclidean graph combinatorially rather than geometrically and (2) proving that the combinatorially contracted graphs have sublinear separators that can be computed in linear time. To prove that the combinatorially contracted graphs have sublinear separators, for each contracted graph we construct an auxiliary Euclidean graph which we call the representative graph of the contracted graph. A representative graph of the contracted graph is a sampled subgraph of the original Euclidean graph. Rather than using the contracted graphs, we use (properties of) their representative graphs to prove that the contracted graphs have sublinear separators.

Moreover, to compute an $r^{\prime }$-division of the contracted graph (for different contracted graphs the parameter $r^{\prime }$ is different), it is normally required that any $k^{\prime }$-vertex subgraph of the contracted graph has a sublinear separator, for any $k^{\prime }$. This is because when dividing the contracted graphs into smaller and smaller pieces, it is required that the smaller pieces still have sublinear separators. However, the contracted graphs of the Euclidean graph classes do not have this property, even if we use their representative graphs to find the separators. Let the contracted graph be $G_i$ and let the accumulated contraction size be the maximum number of vertices in $G$ that are contracted into a vertex in $G_i$. We resolve this critical issue by requiring the division size $r^{\prime }$ to be some constant power of the accumulated contraction size. This requirement forces us to use different parameters for contractions and divisions. This is in contrast to the case in HKRS [12]. Despite this modification, we prove that the effect is sufficient by showing that the induced recursive division is still suitable for applying HKRS’s edge-relaxation algorithm in linear time.

In Section 2 we give preliminaries that are required for later sections. In Section 3 we prove the main theorem. In Sections 4 we consider SSSP in $\tau$-lanky graphs. Due to space limit, we defer the related work section to the full version of the paper. We defer the section of SSSP in the intersection graph of $k$-ply neighborhood system and the section of SSSP in the intersection graph of $\kappa$-thick cubical neighborhood system to the full version of the paper.

Recall that the recursive division can be computed using a two-phase algorithm. In the contraction phase of the recursive division algorithm, the contracted graphs $G_1,G_2,\mathrm{\dots },G_{I+1}$ are constructed consecutively such that $G_i=Contract(G_{i-1},z_{i-1})$, $1\le i\le I+1$, where Contract$(G_{i-1},z_{i-1})$ is the contraction algorithm. For each contracted graph $G_i$, $1\le i\le I+1$, we construct its representative graph $R{G}_i$.

Each edge of $G_i$ has a representative edge in $R{G}_i$, which is an edge in $G$. The representative graph $R{G}_i$ consists of the representative edges of the edges in $G_i$ and their endpoints. The representative edge of an edge $e$ in $G_i$ is denoted as $re{p}_{G_i}(e)$. The representative edge of an edge in $G_0=G$ is the edge itself, and the representative graph of $G_0$ is $G_0$.

The representative graph $R{G}_i$ is constructed from the contracted graph $G_{i-1}$ and its representative graph $R{G}_{i-1}$, as follows. Consider a vertex $u$ in $G_i$ and let $cse{t}_{G_{i-1}}(u)$ denote the connected set of vertices in $G_{i-1}$ from which $u$ is contracted. An edge $e=(u,v)$ in $G_i$ corresponds to the set of edges in $G_{i-1}$ between $cse{t}_{G_{i-1}}(u)$ and $cse{t}_{G_{i-1}}(v)$.

Let $RE{P}_{G_i}(e)=\{re{p}_{G_{i-1}}((u^{\prime },v^{\prime }))|u^{\prime }\in cse{t}_{G_{i-1}}(u),v^{\prime }\in cse{t}_{G_{i-1}}(v),(u^{\prime },v^{\prime })\in E(G_{i-1})\}$ denote the set of the representative edges of the edges in $G_{i-1}$ between $cse{t}_{G_{i-1}}(u)$ and $cse{t}_{G_{i-1}}(v)$. See Figure 2(a) for an illustration. For each edge $e$=$(u,v)$ in $E(G_i)$, choose an arbitrary edge in $RE{P}_{G_i}(e)$ as its representative edge. The chosen representative edges and their endpoints form the representative graph $R{G}_i$ of $G_i$.

According to criterion (II), $R{G}_{i-1}$ has $O(c_3{n}_{i-1})$ edges and vertices. It is then observed that $R{G}_i$ is constructed from $G_{i-1}$ and $R{G}_{i-1}$ in $O(c_3{n}_{i-1})$ time where $n_{i-1}$ is the number of vertices in $G_{i-1}$. Note that $R{G}_i$ may not be connected.

The parameters $z_i$ used in the contraction phase, $0\le i\le I$, are set as in [12]:

Let be the accumulated contraction sizes for the contracted graph $G_i$, and let ${\beta }_{i-1}=z_{i-1}^{3d-2}$. In [12], parameters $z_i$ ($0\le i\le I$) are used for division in the division phase. In contrast, we use ${\beta }_i$ in place of $z_i$ as division parameters in the division phase.

A subgraph of $G_i$ with $O({\alpha }_{i-1})$ vertices may not admit a sublinear separator. However, the next lemma shows that any subgraph of $G_i$ with $\mathrm{\Omega }({\beta }_{i-1})$ vertices admit a sublinear separator.

The recursive division of $G$ is computed in two phases. In the contraction phase, the contraction parameters $z_i$ are set as Equations (2) and (3), and the contracted graphs $G_1,\mathrm{\dots },G_{I+1}$ are computed consecutively by the Contract() algorithm. In the division phase, we choose the parameters for dividing $G_i$, $1\le i\le I+1$, to be ${\beta }_{i-1}=z_{i-1}^{3d-2}$. Since the minimum subgraph of $G_i$ that will be divided has $\mathrm{\Omega }({\beta }_{i-1})$ vertices, we can apply Lemma 11 recursively to obtain the division $D_i$ of $G_i$.

To analyze the computing time of the recursive division, we analyze the division $D_i$ of $G_i$, and the division of $G$ it induces. Recall that the division $D_i$ is derived from the division $D_{i+1}$ of $G_{i+1}$. Let $R_{i+1}$ be a region in $D_{i+1}$. The Divide$(R_{i+1},S_{i+1},{\beta }_i)$ algorithm divides $R_{i+1}$ into subregions each of which has at most ${\beta }_i=z_i^{3d-2}$ vertices and has $O((c_1{c}_3^{1-1/d}+c_4)z_i^{3d-3})$ boundary vertices. Each expanded subregion, which is a region in $D_i$, has at most ${\beta }_i\cdot 3z_i=3z_i^{3d-1}$ vertices and $O((c_1{c}_3^{1-1/d}+c_4)z_i^{3d-2})$ boundary vertices. Let $k_i$ denote the number of regions in the division $D_i$, $0\le i\le I+1$, and let $n_i$ be the number of vertices in $G_i$. We can prove, using similar arguments as in the proof of Lemma 4.1 in [12] that

From the proof of Lemma 12, we can also prove that the sum of the vertices of all regions in $D_i$ is $O(n_i)$. Now we can analyze the computing time of the recursive division of $G$.

We relate the sparsity of the combinatorially contracted graphs of a lanky graph to the graph-theoretic property thickness. The thickness of a graph $G^{\prime }$ is the minimum number of planar subgraphs that $G^{\prime }$ can be decomposed into. Let $\theta (G^{\prime })$ denote the thickness of a graph $G^{\prime }$. Determining the thickness of a general graph is NP-hard [17]. However, for graphs with maximum degree $\mathrm{\Delta }$, Halton [10] proved that if $G^{\prime }$ is a graph with maximum degree $\mathrm{\Delta }$ then $\theta (G^{\prime })\le \lceil \mathrm{\Delta }/2\rceil$. It follows from the definition of lanky graph that a $\tau$-lanky graph $G$ has maximum degree $\tau$. Therefore the thickness of $G$ is at most $\lceil \tau /2\rceil$.

Thus, the $\tau$-lanky graph $G$ can be decomposed into $\lceil \tau /2\rceil$ planar subgraphs, which we call $H_1,\mathrm{\dots },H_{\lceil \tau /2\rceil }$. Let each of $H_1,\mathrm{\dots },H_{\lceil \tau /2\rceil }$ have $V(G)$ as its vertex set. Use the clustering inside the Contract$(G,z_0)$ algorithm to cluster vertices in $V(G)$. For each $H_j$, $1\le j\le \lceil \tau /2\rceil$, shrink each cluster into a vertex while retaining edges between the clusters (shrunk vertices). Let Shrink$(H_j,z_0)$ be the shrunk graph of $H_j$. Then Contract$(G,z_0)$ is the union of Shrink$(H_j,z_0)$, $1\le j\le \lceil \tau /2\rceil$ (removing multi-edges).

Since Shrink$(H_j,z_0)$ is a planar graph, $G_1=Contract(G,z_0)$ has $O(\tau n_1)$ edges where $n_1$ is the number of vertices in $G_1$. Similarly $G_i$, $i\ge 2$, is the union of the iteratively shrunk graphs of $H_j$, $1\le j\le \lceil \tau /2\rceil$, thus has $O(\tau n_i)$ edges where $n_i$ is the number of vertices in $G_i$.

Following similar ideas, we get:

This justifies that a $\tau$-lanky graph satisfies criterion (II) with $c_3=\tau$.

Since $G$ has maximum degree $\tau$, $G$ has $O(\tau n)$ edges so $c_0=\tau$. Plugging the constants into Theorem 15, we have

As a corollary, we get