Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs

Minor-free graphs and geometric intersection graphs are two classes of graphs that share a surprisingly geometric property: they have very natural set systems that have bounded VC-dimension. We can algorithmically exploit these set systems to design algorithms and data structures not possible in general graphs such as subquadratic time algorithms for diameter and subquadratic space data structures for distance oracles.

In this talk, I will discuss several ways in which one can transform planar/minor-free metrics into some simpler object. One helpful tool in this area is the “buffered cop decomposition”, a new way of partitioning minor-free graphs which we recently introduced [1]. I will try to convey some intuition about this structural result, and additionally sketch several applications including $O(1)$-distortion Steiner point removal [1] and optimal $O(\log r)$ padded decomposition for $K_r$-minor-free graphs [2].

For $n$ points in Euclidean plane, several constructions are known for $(1+\epsilon )$-spanners: $\mathrm{\Theta }$-graphs, Yao-graphs, Greedy spanners, and WSPD-based spanners. As $\epsilon \to 0$ an $(1+\epsilon )$-spanner will inevitably have many edge crossings. If we allow Steiner points, we can subdivide the edges at crossing points and obtain a plane $(1+\epsilon )$-spanner. How many Steiner points do we really need?

Let $s(n,\epsilon )$ be the minimum integer such that every set of $n$ points in the plane admits a plane $(1+\epsilon )$-spanner with at most $s(n,\epsilon )$ Steiner points.

Problem Setup: We have an undirected graph $G$. (You can assume the graph is either weighted or unweighted, whichever is more convenient for what you’re trying to prove.) Assume that for every pair of vertices there is one unique shortest path. Each edge also has a unique “capacity” that is hidden from us. We are allowed to choose vertices to “query”. When we query a vertex $s$ then for every vertex $t$ the capacity of the minimum capacity edge on the shortest $st$-path is revealed.

Let OPT be the maximum number of edges that could be revealed by performing a single query in $G$. Note that OPT since any shortest paths tree has edges.

All graphs are unweighted. For a graph $G$ and a vertex subset $X\subseteq G$ we call $X$ $(k,r)$-coverable if $X$ can be covered by $k$ balls of radius $r$ in $G$. Motivated by the talk of Édouard, we pose the following.

Given a set $P$ of $n$ points in the plane, a geometric graph $G(P,E)$ is a graph whose vertex set is $P$ whose edges are segments joining pairs of vertices and edges are typically weighted by their length. A geometric graph $H$ is a $t$-spanner of $G$ if $H$ is a subgraph of $G$ and $\forall xy\in E,d_H(x,y)\le t|xy|$ for some $t\ge 1$, where $d_H(x,y)$ is the length of the shortest path from $x$ to $y$ in $H$. The smallest value of $t$ that satisfies this property is called the spanning ratio of $H$. The graph $G$ is the underlying graph of the $t$-spanner $H$. In this setting the underlying graph is the complete geometric graph.

An online routing algorithm $A$ is an algorithm that forwards a message from its current vertex $s$ to a destination vertex $t$ where the forwarding decision is made as a function of $s$, $t$, $I(s)$ and $M$ where $s$ is the coordinates of the current vertex, $t$ is the coordinates of the destination vertex, $I(s)$ is information stored with vertex $s$ in $G$ and $M$ is some bits of information stored in $A$. Typically, $I(s)$ is the set of vertices adjacent to $s$ in $G$ but sometimes some additional information is stored. The routing ratio of an algorithm $A$ is the maximum spanning ratio among all $s,t$ pairs of the path followed by $A$ from $s$ to $t$ in $G$. Thus the routing ratio is an upper bound on the spanning ratio.

The following are some questions regarding spanners where $G$ is the complete geometric graph and $H$ is a planar spanning subgraph of $G$.

• $\mathrm{■}$

  The spanning ratio of the standard Delaunay triangulation on a set of points is at most $1.998$ and in some cases it is at least $1.59$. Can we improve the upper or lower bound?

• $\mathrm{■}$

  For points in convex position, the upper bound is $1.83$ and the lower bound remains $1.59$. Can we improve either bound?

• $\mathrm{■}$

  Is there a plane spanner with maximum degree 3 and constant spanning ratio? The lowest known degree bound is $4$.

• $\mathrm{■}$

  Can we find a bounded degree plane spanner with spanning ratio better than $2.91$. Currently, the best known bound is degree 14 and spanning ratio 2.91. The best known upper bound on the spanning ratio for spanners with maximum degree less than 10 is a degree bound of 8 and spanning ratio $4.41$.

• $\mathrm{■}$

  For standard Delaunay graphs, the routing ratio is at most $3.5$ and at least $1.7$. Can these bounds be improved?

• $\mathrm{■}$

  Tight spanning ratios of $2.6$ and $2$ are known for Delaunay graphs where the empty circle is replaced by a square and hexagon, respectively. However, the routing ratio on these graphs is $\sqrt{10}$ and $6.4$ respectively which leaves a large gap with the spanning ratio.

Let $G=(V,E)$ be an undirected unweighted planar graph with $n$ vertices, and let $S=\{s_1,\mathrm{\dots },s_k\}$ be the (ordered clockwise) vertices of one face of $G$. Let $d(\cdot ,\cdot )$ denote the shortest path metric of $G$ The pattern $p_v$ of a vertex $v\in V$ is the vector

Note that as the graph is unweighted and the vertices $s_1,\mathrm{\dots },s_k$ are adjacent on one face of $G$ the entries of $p_v$ are in $\{1,0,-1\}$. Since there are $n$ vertices in $G$ there are $n$ patterns. However, Li and Parter [3] showed (using VC dimension type arguments) that there are only at most $O(k^3)$ many distinct patterns:

Given an Euclidean point set $P$ say in ${ℝ}^2$ an emulator for $P$ with stretch $1+ϵ$ is a graph $G=(V,E)$ where $P\subseteq V$ such that $\parallel x,y{\parallel }_2\le d_G(x,y)\le (1+ϵ)\cdot \parallel x,y{\parallel }_2$ for every pair of points $x,y\in P$ How many edges does $G$ have to have?

Note that vertices in $V\setminus P$ do not have to be points in ${ℝ}^2$.

If $V\setminus P$ are restricted be points in ${ℝ}^2$ then we know the answer: $O(n/\sqrt{ϵ})$ edges are both necessary and sufficient. Nothing is known when $V\setminus P$ are not restricted to be points in ${ℝ}^2$.

Here is an embarrassingly simple case: points in $P$ are on two opposite sides of a unit square, and for each side, there are $n=O(1/\sqrt{ϵ})$ points, where the distance between any two consecutive points is $\sqrt{ϵ}$. The complete bipartite graph, which only use points in $P$ and has stretch $1$ has $O(1/ϵ)=O(n/\sqrt{ϵ})$ edges. Could we beat this bound, using points that are not in $P$ (and also not in ${ℝ}^2$)?

A tree cover for a metric space $(X,d)$ is a collection of trees $𝒯$ such that for any two points $p,q\in X$ the following two conditions are true:

• $\mathrm{■}$

  for every tree $T\in 𝒯$ $d(p,q)\le d_T(p,q)$;

• $\mathrm{■}$

  there is a tree $T\in 𝒯$ such that $d_T(p,q)\le \alpha \cdot d(p,q)$.

The tree cover is called to have distortion $\alpha$.

Tree covers are known to exist for many settings:

• $\mathrm{■}$

  $d$-dimensional Euclidean space: $(1+ϵ)$-tree cover with $O({ϵ}^{\frac{(-d+1)}{2}}\log (\frac{1}{ϵ}))$ trees. [1]

• $\mathrm{■}$

  Doubling metrics: $(1+ϵ)$-tree cover with $O({ϵ}^{-d}\log (\frac{1}{ϵ}))$ trees. [2]

• $\mathrm{■}$

  Planar graphs: $(1+ϵ)$-tree cover with $O(1)$ trees. [3]

For unit disk graphs, notice that by using the tree cover of planar graphs, one can immediately construct a $O(1)$-tree cover with $O(1)$ trees, by using a constant planar spanner and then results on planar graphs (e.g., [3]). Naturally one can ask, can we find a $(1+ϵ)$-tree cover for unweighted unit disk graphs? Through personal communication during the seminar, there seems to be already ongoing work towards resolving the aforementioned question. What is still open is whether such a tree cover can be found for unit ball graphs.

A second question to ask is, what is the best stretch factor one can get to approximate a unit disk graph (or a general geometric intersection graph) by a planar graph?

For unit disk graphs, if we want to take a planar spanner graph (using only edges from the input unit disk graph), the known constructions give a stretch factor such as 449 [4] and 341 [5]. Recently we could get a stretch factor of 286 if we allow Steiner vertices. But these stretch factors are still fairly large. Can we do better? What is a lower bound?

A polygonal curve $A:[0,n]\to {ℝ}^d$ consists of $n$ line segments $\overline{a_i{a}_{i+1}}$ for $i=\{0,1,\mathrm{\dots },n-1\}$ where $a_i=A(i)$.

The Fréchet distance between two polygonal curves $A:[0,m]\to {ℝ}^d$ and $B:[0,n]\to {ℝ}^d$ is often described (informally) by the following analogy. Consider a person and a dog connected by a leash, each walking along a curve from its starting point to its end point. Both can control their speed but they are not allowed to backtrack. The Fréchet distance between the two curves is the minimum length of a leash that is sufficient for traversing both curves in this manner (for a formal definition, see below).

The discrete Fréchet distance (DFD for short) is a popular variant in which the two curves are replaced by two sequences of points, and the person and dog are replaced by two frogs, hopping from one point to the next along their respective sequences. The discrete Fréchet distance is defined as the smallest maximum distance between the frogs that can be achieved in such a joint sequence of hops.

Let $G=(V,E)$ be a fixed undirected graph. In the dynamic subgraph connectivity problem each vertex of $G$ is either marked as on or off. An update either turns off a vertex that is on or turns on a vertex that is off. The data structure has to support connectivity queries on the graph induced by the on vertices while vertices are being updated. The dynamic subgraph connectivity problem was introduced in [1]. In [2] the first data structure for general graphs with $O(m^{0.94})$ amortized update time (using FMM) and $\tilde{O}(m^{1/3})$ query time was presented. In [3] the update time of [2] was improved to amortized update time of $\tilde{O}(m^{2/3})$ (without FMM) while keeping the query time $\tilde{O}(m^{1/3})$.

A data structure with $\tilde{O}(m^{4/5})$ worst case update time and $\tilde{O}(m^{1/5})$ query time was presented in [4]. A randomized data structure with $\tilde{O}(m^{3/4})$ worst case update time and $\tilde{O}(m^{1/4})$ query time was presented in [5]. Notice that the product of the update time and the query time is $\tilde{O}(m)$ in all these results.

This is not a coincidence since there is CLB presented by [6] which states that there is no algorithm with polynomial preprocessing time, $O(m^{\gamma -\mathrm{\Omega }(1)})$ amortized update time, and $O(m^{1-\gamma -\mathrm{\Omega }(1)})$ amortized query time, for any constants $0\le \gamma \le 1$ as long as $m\le \min (n^{1/\gamma },n^{1/(1-\gamma )})$.

A banyan of a point set $P\subset {ℝ}^d$ is a geometric graph $G$ where for any terminal set $K\subset P$ we have that $G$ contains a subtree covering $K$ whose weight is at most $1+ϵ$ times the weight of the minimum Euclidean Steiner tree of $K$. (The minimum Euclidean Steiner tree of $K$ is the connected geometric graph of minimum weight that contains $K$ in its vertex set.)

A $k$-banyan is as above, but we only require the property for sets $K$ of size at most $k$. With this definition, $2$-banyans are simply (Steiner) spanners.

• $\mathrm{■}$

  What is the best trade-off between the banyan stretch and the number of Steiner vertices (or the number of edges) of a ($k-$)banyan for a given dimension $d$ What about $3$-banyans?

• $\mathrm{■}$

  What metrics allow light ($k-$)banyans? What is the optimal lightness in ${ℝ}^d$?

There is plenty of work on Steiner spanners, so the case $k=2$ is well-studied and we have good answers for the optimal sparsity and lightness for fixed $d$ in this case. Light banyans have been constructed in a handful of papers cited below, but with the goal of using them for Steiner tree/forest algorithms; I suspect that these constructions are far from optimal in terms of stretch/edge count and stretch/lightness trade-offs.

Starting points are: [1, 2, 3]. The appendix of [4] may also be relevant.

We are given a sequence of points $(s_1,\mathrm{\dots },s_n)$ in a metric space, where the points are presented one-by-one, i.e., point $s_i$ is revealed at step $i$ and $S_i=\{s_1,\mathrm{\dots },s_i\}$ for $i\in \{1,\mathrm{\dots },n\}$. The objective of an online spanner algorithm is to maintain a $t$spanner $G_i$ for $S_i$ for all $i$. The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. Moreover, the algorithm does not know the total number of points in advance. The performance of an online $t$spanner algorithm is measured by comparing it with the offline optimum using the standard notion of competitive ratio, which is defined as ${sup}_{\sigma }\frac{ALG(\sigma )}{OPT(\sigma )}$, where the supremum is taken over all input sequences $\sigma$, $OPT(\sigma )$ is the minimum weight of a $t$spanner for the (unordered) set of points in $\sigma$, and $ALG(\sigma )$ denotes the weight of the $t$spanner produced by the algorithm. Note that, to measure the competitive ratio, it is important that $\sigma$ is a finite sequence of points.

For any set $S$ of $n$ points in Euclidean plane and $\epsilon >0$ one can construct a Steiner $(1+\epsilon )$-spanner of lightness $O({\epsilon }^{-1})$ where the lightness is the ratio between the weight of the spanner and the weight of an MST for the same point set. This bound is the best possible in the plane. In dimensions $d\ge 3$, however, the current best upper and lower bounds do not match: $\mathrm{\Omega }({\epsilon }^{-d/2})$ and $\tilde{O}({\epsilon }^{(1-d)/2})$.