Geometric Spanners of Bounded Tree-Width

Geometric spanners are an extensively studied area in computational geometry, see [7, 23] for surveys. A geometric spanner for a point set $P\in {ℝ}^d$ is a weighted graph on $P$, where the weight of an edge is the Euclidean distance between its endpoints, aiming for sparsity while avoiding long paths between two points in $P$. This is formalised by the dilation $t=\max \left\{\frac{d(p,p^{\prime })}{|p{p}^{\prime }|}\mid p,p^{\prime }\in P\right\}$, where $d(p,p^{\prime })$ is the distance between two points in $G$ and $|p{p}^{\prime }|$ is the Euclidean distance between $p$ and $p^{\prime }$. A geometric spanner with dilation at most $t$ is also called a $t$-spanner.

When geometric spanners were introduced in 1986 [12], sparsity was obtained by requiring planarity. Since then, plane geometric spanners have been widely studied [7]. But also other measures are of interest: Especially spanners with a linearly bounded number of edges or a bounded vertex degree have been widely researched [20, 23, 30, 18, 6, 14, 19, 5].

In graph theory, an important tool to design efficient algorithms for in general NP-hard problems is to restrict these problems to graphs which are bounded in certain parameters. Especially graphs with bounded tree-width [25, 26] allow polynomial-time algorithms for many in general NP-hard problems using a dynamic programming algorithm on the tree decomposition. By Courcelle’s Theorem, every problem that is describable in monadic second order logic with vertex and edge quantification is solvable in polynomial time for graphs with bounded tree-width [13]. Thus, geometric spanners with bounded tree-width would allow polynomial time solutions for many in general NP-hard problems and thus be a strong tool for many geometric applications. For instance, Cabello and Knauer [9] recently gave some examples for efficient algorithms for geometric problems on graphs with bounded tree-width. They show that via orthogonal range searching, for graphs of $n$ vertices and tree-width $k$ with $k\ge 3$, the sum of the distances between all pairs of vertices can be computed in $𝒪(n{\log }^{k-1}n)$ time. Further, they show that the dilation of a geometric graph of bounded tree-width can be computed in $𝒪(n{\log }^{k+1}n)$ time. That makes it possible to compute the dilation of every tree-width bounded graph, but does not lead to tree-width bounded spanners with low dilation. In [8], Cabello shows how to compute the inverse geodesic length in graphs of bounded tree-width. Further, Cabello and Rote [10] show how to compute obnoxious centers in graphs with bounded tree-width in $𝒪(n\log n)$ time.

Therefore, we aim to construct spanners with bounded tree-width. There are spanners with sublinear tree-width. More specifically, since planar graphs have tree-width $𝒪(\sqrt{n})$ [22] (where $n$ is the number of vertices), for point sets in the Euclidean plane, constant dilation spanners with tree-width $𝒪(\sqrt{n})$ can be obtained by plane spanner approaches such as the Delaunay triangulation or the greedy triangulation. For point sets in ${ℝ}^d$, we point out that the greedy spanner has tree-width $𝒪(n^{1-1/d})$, using separator results from [21].

While this gives some first results, constructing spanners with tree-width $k\in o(n^{1-1/d})$ will require other constructions. The only known construction for small tree-width and a guarantee on the dilation is the Euclidean minimum spanning tree: it has tree-width $k=1$ and worst-case dilation $n-1$.

We present a first algorithm that provides a trade-off between tree-width and the dilation:

We complement our result with a matching lower bound.

This proves that our algorithm for Theorem 1 has a worst-case optimal trade off between tree-width and dilation. We therefore now turn our attention to bounded tree-width spanners with an additional property. The most commonly studied property of geometric spanners is planarity.

For point sets in the Euclidean plane, we can adapt the construction of the spanner for Theorem 1 to obtain a planar spanner with bounded tree-width (and bounded degree), that is not necessarily plane. As a general tool to obtain bounded tree-width plane spanners, we provide the following strong dependency between tree-width and the number of edges in sparse connected planar graphs:

This result is quite surprising, since for non-planar graphs, arbitrarily placed edges increase the tree-width linearly in the number of added edges, as there are graphs with $m$ edges and tree-width at least $m\cdot \epsilon$ for a constant $\epsilon$ [17].

It further yields an alternative proof for Theorem 1 for $d=2$, creating a bounded tree-width spanner with additional properties:

This follows immediately using an adapted version of the algorithm provided in [3]: Instead of the Delaunay triangulation, use a plane constant dilation spanner with maximum vertex degree $4$, as provided in [19] and the MST of this spanner instead of the EMST.

In the last section, we answer an open question stated in [3] by giving some smaller results for spanners of bounded tree-width on points in convex position. In particular, we show that, for point sets $P$ which are equally spaced on a circle, there is a tree spanner with dilation $\le \frac{2n}{\pi }+\frac{\pi }{2n}$. This complements a lower bound given in [3]. Further, since plane spanners on points in convex position are outerplanar, there is a $1.88$-spanner of tree-width $2$ for $P$. Further, we give a (straight-forward) lower bound: There are sets of points in convex position on which every spanner of tree-width $2$ has dilation at least $1.43$.

We start giving some preliminary definitions to clarify the notations we use later on.

In this paper, all graphs $G$ are simple and undirected. We refer to the vertex set of $G$ by $V(G)$ and to the edge set of $G$ by $E(G)$. Euclidean graphs are complete and weighted and the edge weight is given by the Euclidean distance of the incident vertices. We denote the degree of a vertex $v\in V(G)$ by ${\mathrm{\Delta }}_G(v)$ and the maximum vertex degree of a graph by $\mathrm{\Delta }(G)$. By $K_n$ we denote the complete graph on $n$ vertices.

A Euclidean $2$-dimensional $n\times n$-grid is defined as a graph on the point set $\{0,\mathrm{\dots },n-1\}\times \{0,\mathrm{\dots },n-1\}$ in ${ℝ}^2$. We call two vertices $(x,y)$ and $(x^{\prime },y^{\prime })$ neighbouring, if $|x-x^{\prime }|+|y-y^{\prime }|=1$. The edge set of the $n\times n$ grid is then $\{\{(x,y),(x^{\prime },y^{\prime })\}\mid (x,y)\text{ and }(x^{\prime },y^{\prime })\text{ are neighbouring}\}$.

A Euclidean $d$-dimensional $n^d$-grid is defined as a graph on the point set ${\{0,\mathrm{\dots },n-1\}}^d$. Here, two vertices $(x_1,\mathrm{\dots },x_d)$ and $(x_1^{\prime },\mathrm{\dots },x_d^{\prime })$ are called neighbouring if $|x_1-x_1^{\prime }|+\mathrm{\cdots }+|x_d-x_d^{\prime }|=1$. The edge set of the $n^d$ grid is then $\{\{(x_1,\mathrm{\dots }{x}_d),(x_1^{\prime },\mathrm{\dots },x_d^{\prime })\}\mid (x_1,\mathrm{\dots }{x}_d)\text{ and }(x_1^{\prime },\mathrm{\dots }{x}_d^{\prime })\text{ are neighbouring}\}$.

We use a standard definition of tree-width [26] in the following notation: A tree decomposition $(T,X)$ is a tree $T$ over a set of nodes $I$ and a mapping $X:I\to 2^V$, where $X(i)$ is called the bag of $i$, so that the following conditions hold:

1. 1.

   ${\bigcup }_{i\in I}X(i)=V$

2. 2.

   ${\bigcup }_{i\in I}E(i)=E$ where $E(i)=\{\{u,v\}\in E\mid u,v\in X(i)\}$

3. 3.

   If $v\in X(i)$ and $v\in X(k)$ for some $i,k\in I$ then $v\in X(j)$ holds for every $j$ on the path in $T$ between $i$ and $k$.

The width of a tree decomposition is defined as ${\max }_{i\in I}|X(i)|-1$. The tree-width $\text{tw}(G)$ of $G$ is the minimum width over all tree decompositions of $G$.

A minor of a graph can be obtained by subgraph operations and edge contractions. As, however, edge contractions in general do not maintain any properties of the embedding, which is essential for geometric graphs, we give the definition of contracting one vertex to another: For a graph $G$, contracting vertex $u$ to $v$ or equivalently contracting vertex $u$ along $e$, we create a minor $G^{\prime }=(V^{\prime },E^{\prime })$ of $G$ with $V^{\prime }=V\setminus \{u\}$ and $E^{\prime }=\{\{u^{\prime },v^{\prime }\}\mid u^{\prime },v^{\prime }\in V^{\prime },\{u^{\prime },v^{\prime }\}\in E\}\cup \{\{u^{\prime },v\}\mid u^{\prime }\ne v,\{u^{\prime },u\}\in E\}$. Note that this is just another way of defining an edge contraction. Given a graph $G=(V,E)$, some vertex $v\in V$ and a path $\gamma =v,v_2,\mathrm{\dots },v_{\mathrm{\ell }}$ inside $G$, we define the path contraction of $\gamma$ to $v$ to be the series of vertex contractions starting with the contraction of $v_2$ to $v$ up to the contraction of $v_{\mathrm{\ell }}$ to $v$. A graph $H$ is a minor of $G$ if it can be obtained by vertex contractions and subgraph operations. A class of graphs $𝒢$ is considered minor closed if every minor $H$ of a graph $G\in 𝒢$ is also in $𝒢$.

A $t$-balanced separator of size $s$ of a graph $G$ is an edge set $S\subseteq V(G)$, $|S|=s$ such that $V-S$ can be partitioned into two sets $A$ and $B$ with no edges between the vertices of $A$ and $B$ and $|A|\le t\cdot |V|$ as well as $|B|\le t\cdot |V|$. If $t=\frac{2}{3}$, we call $S$ a separator of $G$.

In this section, we present an algorithm for constructing bounded tree-width spanners for points in ${ℝ}^d$ for constant dimension $d$. As we will see later on, the trade-off between tree-width and dilation of this spanner is worst-case optimal.

The algorithm makes use of two ingredients: a Euclidean minimum spanning tree ($ℰℳ𝒮𝒯$) and a class of spanners with sublinear tree-width. For $d=2$ a class of planar spanners can be used (and will be used in Section 5). For general $d$ we can use the greedy spanner [2] instead.

The following algorithm computes a bounded tree-width spanner. The constant $C$ is defined as $C=30{\eta }_d{c}_d{8}^d$.

We now start with a detailed description on how the subtrees (line 5) are constructed.

The following is a folklore result and is for instance mentioned in [22].

Considering the separator vertex $v$ and its edges, we observe that one of the by removal of $v$ induced subtrees must have size at least $n\cdot 1/\mathrm{\Delta }(v)$. Let $e$ be the edge that connects $v$ to this subtree. Then, $e$ separates the tree into one subtree of size at least $n\cdot 1/\mathrm{\Delta }(v)$, this being the aforementioned subtree, and one of size at most $n\cdot (\mathrm{\Delta }(v)-1)/\mathrm{\Delta }(v)$.

This result can be extended as follows:

In the previous section it was shown that Algorithm 1 gives an upper bound for the dilation of tree-width bounded spanners. In this section, we investigate corresponding lower bounds. We show that the bound given in Theorem 1 for the dilation of a tree-width bounded spanner on Euclidean point sets is asymptotically tight:

See 2

To obtain this result, we construct a set of points resembling a grid. While it is commonly known that a two-dimensional grid has high tree-width, the ${\left(k^{1/(d-1)}\right)}^d$-grid does not necessarily have tree-width $k$. We thus construct a set of points resembling the ${(h+1)}^d$-grid, where $h=\lceil {(9d/2\cdot (k+2))}^{1/(d-1)}-1\rceil$. To lower bound the tree-width of this grid, we generalise a basic idea for the $3$-dimensional grid given by Korhonen in an online forum¹¹1https://cstheory.stackexchange.com/questions/53029/what-is-the-treewidth-of-the-3d-grid-mesh-
or-lattice-with-sidelength-n:

Thus, the tree-width of our grid is at least

Using an inductive construction for the ${(h+1)}^d$-grid, by taking $d$ copies of the ${(h+1)}^{d-1}$-grid and connecting them using $(d-1)\cdot {(h+1)}^{d-1}$ edges, we can prove that the ${(h+1)}^d$-grid has a total of $d\cdot {(h+1)}^d+d\cdot {(h+1)}^{d-1}$ edges.

The constructing of the grid-like set $P_{d,n,k}$ is as follows: Let $m=\lfloor n/(d\cdot {(h+1)}^d+d\cdot {(h+1)}^{d-1})\rfloor$, be the number of points representing an edge of the grid in $P_{d,n,k}$. For every dimension $i\in \{1,\mathrm{\dots },d\}$, we define the set

which consists of ${(h+1)}^{d-1}$ sets of collinear points representing the grid edges parallel to the axis of the $i$-th dimension. Each of these collinear sets of points consists of $h\cdot m+1$ points and represents $h$ edges of the grid. Hence $|P_i|=(h\cdot m+1)\cdot {(h+1)}^{d-1}$ for every $i$. We can now define the set $P_{d,n,k}={\bigcup }_{i=1}^d{P}_i$ which represents the whole ${(h+1)}^d$-grid. (In Figure 1 an example is shown for a $2$-dimensional point set.) Notice that the ${(h+1)}^d$ points $P_{⊞}=\{(j_1\cdot m,\mathrm{\dots },j_d\cdot m)\mid j_1,\mathrm{\dots },j_d\in \{0,\mathrm{\dots },h\}\}$ are contained in every $P_i$. We call these points the grid points of the set $P_{d,n,k}$ and two grid points are called neighbouring if the Euclidean distance between them is $m$, which corresponds to them being connected through an edge in the ${(h+1)}^d$-grid.

We now have given an asymptotically tight algorithm to obtain small bounded tree-width, with a dilation dependent on the chosen tree-width. We now focus on bounded tree-width spanners with the additional property of being plane.

In general, there are graphs with $m$ edges and tree-width at least $m\cdot \epsilon$ for a constant $\epsilon$ [17]. We show that this is not true for connected planar graphs, yielding a tight dependency between tree-width and the number of edges:

See 3

We have seen that for unrestricted sets of points in the plane the Delaunay triangulation is an $1.998$-spanner of tree-width $6\sqrt{n}+1$. To obtain spanners with smaller tree-widths, we now look at sets of points in the plane that are convex or even lie on a circle.

In this paper, we give the first algorithm for computing geometric spanners with bounded tree-width for points in Euclidean space of constant dimension. Further, we show a strong dependency between the tree-width and the number of edges in connected planar graphs with few edges.

Our lower bound proves that the dilation of our spanner is worst-case optimal for tree-width $k$. This naturally leads to the question of optimisation: Given a set of points and a parameter $k$, can we compute the minimum-dilation spanner of tree-width $k$? Already for $k=1$, that is for minimum-dilation trees, the problem is NP-hard [20, 11]. This raises the question of approximation: Can we efficiently approximate the minimum-dilation spanner of tree-width $k$ in terms of its dilation within a factor better than $𝒪(n/k^{d/d-1})$? As a bicriteria problem, the tree-width of the approximation may also be $f(k)$ for a suitable function $f$.