Algorithms for Distance Problems
in Continuous Graphs

Consider an edge-weighted, connected graph $G=(V(G),E(G),\mathrm{\ell })$,where $\mathrm{\ell }$ is a function that assigns a length $\mathrm{\ell }(e)\ge 0$ to each edge $e\in E(G)$ (clearly, for our purposes we assume that not all edge lengths are 0). Informally, the continuous graph $𝒢$ defined by $G$ is the infinite set of points determined by the vertices and edges of $G$, where each point on an edge is part of the graph. This idea requires to define precisely what we mean by a point on an edge.

For each edge $uv$ of $G$, we take a closed segment of length $\mathrm{\ell }(uv)$ with the usual metric and measure, and denote it $𝒢(uv)$. Moreover, for such an edge $uv$, we arbitrarily select one extreme of the segment $𝒢(uv)$ and denote it $\mathrm{endp}(uv,u)$, and call $\mathrm{endp}(uv,v)$ the other endpoint of $𝒢(uv)$. Finally, for each vertex $u$ of $G$, we glue (mathematically, we identify) all points $\mathrm{endp}(uv,u)$ over all edges $uv$ of $G$ incident to $u$; we denote by $𝒢(u)$ the identified point. The continuous graph $𝒢$ defined by $G=(V(G),E(G),\mathrm{\ell })$ is the resulting space. The total length $\mathrm{\ell }(𝒢)$ of a continuous graph $𝒢$ defined by a graph $G$ is defined as ${\sum }_{uv\in E(G)}\mathrm{\ell }(uv)$.

We observe that one may think of $𝒢$ as a $1$-dimensional simplicial complex where each edge $uv$ is isometric to a segment of length $\mathrm{\ell }(uv)$.

A point $p$ of $𝒢$ can be specified by a triple $(uv,u,\lambda )\in E(G)\times V(G)\times [0,\mathrm{\ell }(uv)]$, which represents the point of the segment $𝒢(uv)$ at distance $\lambda$ (along $𝒢(uv)$) from the endpoint $\mathrm{endp}(uv,u)$. The triples $(uv,u,\lambda )$ and $(uv,v,\mathrm{\ell }(uv)-\lambda )$ define the same point of $𝒢$. Similarly, for any two incident edges $uv,u{v}^{\prime }$ of $G$, the triples $(uv,u,0)$, $(uv,v,\mathrm{\ell }(uv))$, $(u{v}^{\prime },u,0)$ and $(u{v}^{\prime },v^{\prime },\mathrm{\ell }(u{v}^{\prime }))$ define the same point, namely $𝒢(u)$.

We have already set the notation $𝒢(uv)$ for an edge $uv$ and $𝒢(u)$ for a vertex $u$. With a slight abuse of notation, we do not distinguish $uv$ from $𝒢(uv)$ and $u$ from $𝒢(u)$.

In general, for any subgraph $H$ of $G$, we denote by $𝒢(H)$ the continuous subgraph of $𝒢$ defined by the objects of $H$. This is also the continuous graph defined by $H$. Also, when $H$ is clear from the context, we denote such an object by $\mathscr{H}$ and talk about $\mathscr{H}$ as a subgraph of $𝒢$. For a vertex set $A\subseteq V(G)$, we use $G[A]$ to denote the subgraph of $G$ induced by $A$.

A walk in $𝒢$ between two points $p,q\in 𝒢$ is a sequence $p{v}_1,v_1{v}_2,\mathrm{\dots },v_{k-1}{v}_k,v_{k}q$ with $v_1{v}_2,\mathrm{\dots },v_{k-1}{v}_k\in E(G)$. If the first and last point coincide, it is closed. The length of a walk is the sum of the length of its pieces, counted with multiplicity. For any two points $p,q\in 𝒢$, the distance $d_{𝒢}(p,q)$ is the minimum length over all $p$-to-$q$ walks. A shortest $pq$-path is a $p$-to-$q$ walk $\pi (p,q)$ in $𝒢$ such that $\mathrm{\ell }(\pi (p,q))=d_{𝒢}(p,q)$.

We can regard $d_{𝒢}(p,q)$ as the discrete graph-theoretic distance in a graph obtained by subdividing $a{a}^{\prime }$ with $p$ as a new vertex, subdividing $b{b}^{\prime }$ with $q$ as a new vertex, and setting $\mathrm{\ell }(ap)=\lambda$, $\mathrm{\ell }(p{a}^{\prime })=\mathrm{\ell }(a{a}^{\prime })-\lambda$, $\mathrm{\ell }(bq)={\lambda }^{\prime }$, and $\mathrm{\ell }(q{b}^{\prime })=\mathrm{\ell }(b{b}^{\prime })-{\lambda }^{\prime }$.

Consider a continuous graph $𝒢$ defined by a graph $G$ and a continuous subgraph $\mathscr{H}\subseteq 𝒢$ defined by a subgraph $H\subseteq G$. We are interested in distances between points of $\mathscr{H}$ using the metric given by $𝒢$. One may think of $𝒢$ as the ambient space and of $\mathscr{H}$ as the relevant subset.

The eccentricity of a point $p\in \mathscr{H}$ with respect to $\mathscr{H}$ is $\mathrm{ecc}(p,\mathscr{H},𝒢)={\max }_{q\in \mathscr{H}}{d}_{𝒢}(p,q)$; when $\mathscr{H}=𝒢$, we just talk about the eccentricity of $p$ in $𝒢$ and write $\mathrm{ecc}(p,𝒢)$ for $\mathrm{ecc}(p,\mathscr{H},𝒢)$. The diameter of $\mathscr{H}$ with respect to $𝒢$ is defined as $\mathrm{diam}(\mathscr{H},𝒢)={\max }_{p,q\in \mathscr{H}}{d}_{𝒢}(p,q)$; when $\mathscr{H}=𝒢$, we just talk about the diameter of $𝒢$ and write $\mathrm{diam}(𝒢)$ for $\mathrm{diam}(𝒢,𝒢)$. It is easy to see that $\mathrm{diam}(\mathscr{H},𝒢)={\max }_{p\in \mathscr{H}}\mathrm{ecc}(p,\mathscr{H},𝒢)$. The sum of distances of $\mathscr{H}$ in $𝒢$ is the sum of the pairwise distances in $\mathscr{H}$, using the metric from $𝒢$, that is, $\mathrm{sumdist}(\mathscr{H},𝒢)={\iint }_{p,q\in \mathscr{H}}{d}_{𝒢}(p,q)𝑑p𝑑q$. The mean distance of $\mathscr{H}$ in $𝒢$ is $\mathrm{mean}(\mathscr{H},𝒢)=\frac{1}{\mathrm{\ell }{(\mathscr{H})}^2}\mathrm{sumdist}(\mathscr{H},𝒢)$. It is easy to see that $\mathrm{mean}(\mathscr{H},𝒢)=\frac{1}{\mathrm{\ell }(\mathscr{H})}{\int }_{p\in \mathscr{H}}\mathrm{mean}(p,\mathscr{H},𝒢)𝑑p$, where $\mathrm{mean}(p,\mathscr{H},𝒢)=\frac{1}{\mathrm{\ell }(\mathscr{H})}{\int }_{q\in \mathscr{H}}{d}_{𝒢}(p,q)𝑑q$ is the mean distance from the point $p\in \mathscr{H}$ with respect to $\mathscr{H}$ in $𝒢$. When $\mathscr{H}=𝒢$, then we just write $\mathrm{mean}(𝒢)$ for $\mathrm{mean}(𝒢,𝒢)$ and $\mathrm{mean}(p,𝒢)$ for $\mathrm{mean}(p,𝒢,𝒢)$.

The treewidth of a graph is an important parameter in algorithmic graph theory which, roughly speaking, measures how far the graph is from being a tree (a formal definition is given in [11]). Graphs of treewidth $k$ have $O(kn)$ edges [6].

A separation in a graph $G$ is a triple $(A,B,S)$ such that $A,B,S\subset V(G)$, $A\cup B=V(G)$, $S=A\cap B$, and there is no edge incident to both $A\setminus B$ and $B\setminus A$. The elements of $S$ in separation $(A,B,S)$ are called portals. Each path in $G$ from $A$ to $B$ must pass through a portal. Informally, we are interested in separations where $A$ and $B$ have a constant fraction of the vertices and $S$ is small. Such separations of at most $k$ portals exist for graphs of treewidth $k$, can be computed in linear time, and have the additional property that adding edges between the portals does not increase the treewidth [8, 12]; . For simplicity, we assume that $S$ contains exactly $k$ portals (it may happen that is has fewer). We use the notation $[k]$$=\{1,\mathrm{\dots },k\}$. We have two regimes, depending on whether we consider the treewidth constant or a parameter.

We use the notation $B(n,d)=\left(\genfrac{}{}{0pt}{}{d+\lceil \log n\rceil }{d}\right)$ to bound the performance of some of our data structures. First we note the following asymptotic bounds.

A rectangle in ${ℝ}^d$ is the Cartesian product of $d$ intervals (whose extremes can be included or not). The analysis of orthogonal range searching performed in [8, Section 3] (see also [28]) leads to the data structure described in the the following theorem. We use the version suggested by Cabello [10] because it adapts better to our needs. (We use $⨆$ to indicate that the union is between pairwise disjoint sets.)

We start with a characterization of the diameter in the continuous setting that uses the length of walks (compare to Figure 1). For each $a{a}^{\prime },b{b}^{\prime }\in E(G)$, let $W(a{a}^{\prime },b{b}^{\prime })$ be a shortest closed walk passing through all the interior points of $a{a}^{\prime }$ and $b{b}^{\prime }$.

The following corollary is an immediate consequence of Lemma 6.

For our computation, we use the following closed formula.

For each pair of oriented edges $(a_0,a_1),(b_0,b_1)\in E(G)$, Lemma 8 implies that there are two possible values for $\mathrm{\ell }(W(a_0{a}_1,b_0{b}_1))$. We say that $(a_0,a_1,b_0,b_1)$ is of type $1$ if

and of type $2$ otherwise. For each oriented edge $(b_0,b_1)\in E(G)$ and type $\tau \in \{1,2\}$, we define

Therefore, $(a_0,a_1)\in {\mathrm{Type}}_1(b_0,b_1)⟺d_G(a_0,b_0)+d_G(a_1,b_1)\le d_G(a_0,b_1)+d_G(a_1,b_0)$.

Let $(A,B,S)$ be a separation in $G$ with $k$ portals. We fix an enumeration $s_1,\mathrm{\dots },s_k$ of them. Let $E_A\subseteq E(G[A])$ be the edge set of the subgraph of $G$ induced by $A$ and $E_B\subseteq E(G[B])$, respectively; not necessarily disjoint. For each index $i\in [k]$, each vertex $a\in A$, and each vertex $b\in B$, let $\phi (i;a,b)$ be the logic predicate that holds whenever $s_i$ is the first portal in the enumeration that lies in some shortest path from $a$ to $b$. Formally,

It is easy to see that, for each $(a,b)\in A\times B$, there exists a unique index $i\in [k]$ where $\phi (i;a,b)$ holds (in other words, $|\{i\in [k]\mid \phi (i;a,b)\}|=1$).

We extend this to the four shortest paths defined by two vertices $a_0,a_1\in A$ and two vertices $b_0,b_1\in B$, by defining the following predicate for all $\kappa =(i_{0,0},i_{0,1},i_{1,0},i_{1,1})\in {[k]}^4$:

Therefore, this predicate holds if and only if, for each $\alpha ,\beta \in \{0,1\}$, the index $i_{\alpha ,\beta }$ is the smallest index $i$ with the property that $s_i$ lies on some shortest path from $a_{\alpha }$ to $b_{\beta }$. As before, for each $(a_0,a_1,b_0,b_1)\in A^2\times B^2$, there exists a unique $4$-tuple $\kappa \in {[k]}^4$ where $\mathrm{\Phi }(\kappa ;a_0,a_1,b_0,b_1)$ holds. For each $\kappa \in {[k]}^4$, each $(b_0,b_1)\in E_B$, and each type $\tau$ we define

This represents the maximum length over all edges $(a_0,a_1)$ of a type-$\tau$ walk between $(b_0,b_1)$ and $(a_0,a_1)$, consistent with the portals in $\kappa$. We next discuss how to compute efficiently ${\mathrm{\Lambda }}_{\tau }(\kappa ;b_0,b_1)$ for several edges $(b_0,b_1)\in E_B$ simultaneously.

Let $G$ be a graph with $n$ vertices and $m$ edges defining the continuous graph $𝒢$. Let $H$ be a subgraph of $G$ defining a continuous graph $\mathscr{H}\subseteq 𝒢$. We use a divide-and-conquer approach to compute $\mathrm{diam}(\mathscr{H},𝒢)$.

Let $(A,B,S)$ be a separation in $G$. Let $G^{\prime }$ be the graph obtained from $G$ by adding an edge $s{s}^{\prime }$ with length $d_G(s,s^{\prime })$ for every pair of portals $s,s^{\prime }\in S$. (If the edge already exists, we redefine its length.) For $X\in \{A,B\}$, let ${\mathscr{H}}_X$ and ${𝒢}_X^{\prime }$ be the continuous graphs defined by $H[X]-E(G[S])$ and $G^{\prime }[X]$, respectively. The edges $s{s}^{\prime }$ added to $G$ guarantee that $d_{𝒢}(p,q)=d_{{𝒢}_X^{\prime }}(p,q)$ for any points $p,q\in {\mathscr{H}}_X$. (We removed $E(G[S])$ because for points on edges between portals whose length is redefined, the statement is undefined.) Therefore

(see Figure 2). The last term can be computed by Lemma 10, which depends on the size of $S$.

Now we have two regimes depending on whether we want to assume that the treewidth is constant, as done in [12], or whether we want to consider the treewidth a parameter, as done in [8]. The same distinction was made in [10]. This difference affects the time to find a tree decomposition and the number of portals in a balanced separation. In both cases we use that an $n$-vertex graph with treewidth $k$ has $O(kn)$ edges [6].

We compute the sum of all distances in a continuous graph as the volume of a collection of triangular prisms. A truncated triangular prism is formed when a prism is sliced by a plane that is not parallel to its bases; the heights are the lengths of the three edges orthogonal to the basis. The volume of a truncated triangular prism with base $\mathrm{△}$ and heights $h_1,h_2,h_3$ is $\frac{1}{3}\mathrm{area}(\mathrm{△})(h_1+h_2+h_3)$.

Consider the following setting defined by a complete graph with vertex set $\{a_0,a_1,b_0,b_1\}$ and variable edge lengths, as follows: (i) $a_0{a}_1$ has variable length $y>0$, (ii) $b_0{b}_1$ has variable length $z>0$, (iii) for all $\alpha ,\beta \in \{0,1\}$, $a_{\alpha }{b}_{\beta }$ has length $x_{\alpha ,\beta }\ge 0$.

Let $K=K(y,z,x_{0,0},x_{0,1},x_{1,0},x_{1,1})$ denote this graph, and let $𝒦$ denote the corresponding continuous graph. See Figure 3. We say that the $6$-tuple $(y,z,x_{0,0},x_{0,1},x_{1,0},x_{1,1})$ is compliant if, for all $\alpha ,\beta \in \{0,1\}$ it holds $x_{\alpha ,\beta }=d_K(a_{\alpha },b_{\beta })$. In our setting we only need to consider compliant cases. (This poses some conditions on the values that the variables can take.)

We want to understand how the total sum of distances between points on $a_0{a}_1$ and $b_0{b}_1$,

looks like. For each $\lambda \in [0,y]$, let $p(\lambda )$ be the point specified by the triple $(a_0{a}_1,a_0,\lambda )$, and, for each $\mu \in [0,z]$, let $q(\mu )$ be the point specified by the triple $(b_0{b}_1,b_0,\mu )$. Then

Function $(\lambda ,\mu )\mapsto d_{𝒦}(p(\lambda ),q(\mu ))$, defined in $[0,y]\times [0,z]$, is the lower envelope of four functions

Following [21], we call the graph of function $(\lambda ,\mu )\mapsto d_{𝒦}(p(\lambda ),q(\mu ))$ a roof; the value $\xi$ is the volume below the roof. The minimization diagram of this function consists of convex pieces; see Figure 3. The gradient of each function is of the form $(\pm 1,\pm 1)$. When the variable values are compliant, all four functions appear in the lower envelope, and the minimization diagram has four regions. (Some of them may contain only part of an edge of the domain.)