Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane

Computing the diameter of sparse graphs is truly subquadratic hard: under the Strong Exponential Time Hypothesis (SETH), there is no $O(n^{2-\epsilon })$ algorithm for distinguishing diameter 2 vs. 3 of graphs with $n$ vertices and $\tilde{O}(n)$¹¹1$\tilde{O}(\cdot )$ hides polylogarithmic factors. edges [20]. This conditional lower bound implies that the trivial algorithm for computing the diameter by doing BFS from every vertex is essentially optimal. Since then, the major research focus has been on substantially beating the BFS-based algorithm for structural families of graphs, especially planar/minor-free graphs and geometric intersection graphs. For planar/minor-free graphs, truly subquadratic algorithms were known [5, 16, 13, 18, 9].

For geometric intersection graphs, the complexity of diameter computation remains poorly understood due to the sheer diversity of geometric objects underlying the intersection graphs, for example, line segments, strings, (unit) disks, triangles, rectangles, balls, hypercubes, (axis-aligned) boxes, to name just a few. Another important subtlety is that intersection graphs can have $\mathrm{\Omega }(n^2)$ edges; therefore, a truly subquadratic time algorithm must use an implicit graph representation. (In a geometric intersection graph, each vertex corresponds to a geometric object, and there is an edge between every two intersecting objects.)

The pioneering work by Bringmann et al. [4] studied computing the diameter of intersection graphs of several types of objects: axis-parallel unit segments, equilateral triangles, axis-parallel hypercubes, and balls. They showed that it is truly subquadratic hard to solve: (i) Diameter-$2$ for axis-parallel hypercubes in ${ℝ}^{12}$ under the Hyperclique Hypothesis; (ii) Diameter-$3$ for (not necessarily axis-aligned) unit segments and equilateral triangles in ${ℝ}^2$ under Orthogonal Vector (OV) Hypothesis; and (iii) Diameter-$\mathrm{\Omega }(\log n)$ for unit balls and axis-parallel unit cubes in ${ℝ}^3$, and axis-parallel line segments in ${ℝ}^2$, all under OV Hypothesis. Here Diameter-$\mathrm{\Delta }$ asks to decide if a given input graph has diameter at most $\mathrm{\Delta }$ or at least $\mathrm{\Delta }+1$. Notably, basic objects such as axis-aligned squares, disks, and their unit versions were absent from this list of lower bounds. However, the same paper showed that Diameter-2 for axis-aligned unit squares can be solved in $O(n\log n)$ time, which hinted at the possibility of truly subquadratic time for other diameter values and objects such as axis-aligned squares and (unit) disks. Later, Duraj, Konieczny, and Potępa [14] gave an algorithm with running time $\tilde{O}(\mathrm{\Delta }{n}^{7/4})$ for Diameter-$\mathrm{\Delta }$ of axis-aligned unit squares: it is truly subquadratic when the true diameter is $O(n^{1/4-\epsilon })$. Chang, Gao, and Le [11] (arXiv version) designed a truly subquadratic $+1$-approximation algorithm for the diameter of axis-aligned unit squares, unit disks, and more generally, similar-sized fat pseudo-disks. Recently, Chan et al. [9] gave algorithms for computing the exact diameter of unit disks and arbitrary axis-aligned squares; the running time is truly subquadratic regardless of the diameter value.

Altogether, the previous work reveals highly contrasting pieces of the complexity landscape of geometric intersection graphs which depend on object types: either computing a very small diameter (e.g., $\mathrm{\Delta }=2$ or $3$) is truly subquadratic hard for some objects, or the diameter can be computed in truly subquadratic time regardless of the value of the diameter for others.

We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. Our results are presented in two papers. The present paper focuses solely on the 2D case. All the previous truly subquadratic algorithms for diameter are for objects on the plane, and hence this basic case is of particular interest. We present numerous results, both positive and negative, on computing the diameter of the geometric intersection graphs of a wide variety of 2D objects. A high-level takeaway from our collection of results is that the complexity of computing the diameter depends not only on object type, but also on diameter range and how the objects intersect.

In the concurrent paper [8], we study objects in dimensions at least $3$ and present various upper and lower bounds. Both papers together show that the landscape of computing the diameter on geometric intersection graphs is much more nuanced than previously known.

A string graph is an intersection graph of curves in the plane. Each curve is called a string. Note that intersection graphs of line segments are string graphs. In this section, we will devote to proving VC-dimension bounds for string graphs that will give subquadratic diameter algorithms for line-segment intersection graphs. Once we have upper bounds for VC-dimension, we can apply (variations of) the algorithmic framework of [9] to obtain subquadratic time algorithms.

Our key technical contribution in this section is a new color-based argument to bound the VC dimension. To set the stage, we need to introduce the notion of canonical curves. Let $G$ be the intersection graph of (connected) objects. For each object $o_x$ corresponding to a vertex $x\in V$, we pick a point $p_x\in o_x$ as a representation of $o_x$. For a path $P$ between two vertices $x$ and $y$ in $G$, there is a planar curve, denoted by ${\sigma }_P$, that connects $p_x\in o_x$ and $p_y\in o_y$, and traces the objects corresponding to the vertices in $P$. We call ${\sigma }_P$ the canonical curve of $P$. For a pair of vertices $x$ and $y$, we define their canonical curve $\sigma (x,y)$ to be the canonical curve of the shortest path in $G$ between $x$ and $y$. (We will fix one arbitrary shortest path per pair to define the canonical curve.) We say that two paths $P$ and $Q$ of $G$ cross on the plane if they do not share any endpoint and their canonical curves intersect in ${ℝ}^2$. Note that $P$ and $Q$ might be vertex-disjoint; see Figure 1(a).

Our starting point is the $K_5$-avoidance argument by Chang, Gao, and Le [11] for showing that the distance VC-dimension of any intersection graph of pseudo-disks is at most 4, which we briefly review here. The proof is by contradiction: suppose that 5 vertices $\{a_1,a_2,\mathrm{\dots },a_5\}$ are shattered, then, for every two points $a_i$ and $a_j$ where $i\ne j\in [5]$, there is a (distinct) vertex $v_{ij}$ whose neighborhood contains $a_i$ and $a_j$ only. The two canonical curves $\sigma (a_i,v_{ij})\circ \sigma (v_{ij},a_j)$ form a curve between $p_{a_i}$ and $p_{a_j}$ on the plane. The set of 5 points ${\{p_{a_i}\}}_{i\in [5]}$ and 10 curves ${\{\sigma (a_i,v_{ij})\circ \sigma (v_{ij},a_j)\}}_{i\ne j\in [5]}$ between these points form a drawing of $K_5$ on the plane. Then, by the Hanani–Tutte theorem, there exist two curves that do not share endpoints and cross (an odd number of times). Consequently, there exists $v_{ij}$ and $v_{cd}$ for four distinct indices $i,j,c,d\in [5]$ such that ${\pi }_G(v_{ij},a_i)$ and ${\pi }_G(v_{cd},a_c)$ cross on the plane. Using the fact that objects are pseudo-disks, they conclude that either (i) $|{\pi }_G(v_{cd},a_i)|\le |{\pi }_G(v_{cd},a_c)|$ or (ii) $|{\pi }_G(v_{ij},a_c)|\le |{\pi }_G(v_{ij},a_i)|$; see Figure 1(b). In the former case, the neighborhood of $v_{cd}$ contains $a_i$, contradicting that $v_{cd}$ only contains $a_c$ and $a_d$; in the latter case, the neighborhood of $v_{ij}$ contains $a_c$, contradicting that $v_{ij}$ only contains $a_i$ and $a_j$. The last part of the argument depends crucially on the fact that objects are pseudo-disks, and therefore, does not apply to strings and line segments (which are not pseudo-disks).

Here, we devise a new argument based on vertex coloring on top of the $K_5$-avoidance technique. Our idea is best illustrated in the case of bipartite string graphs $G=(A\cup B,E)$ (in Section 3.1). Specifically, each vertex can be colored as $A$ or $B$, depending on which side it belongs to. Then we can view each canonical curve $\sigma (a_i,v_{ij})$ as a sequence $S_{ij}$ of alternating colors: $S_{ij}=ABAB\mathrm{\dots }$. Following the setup of the $K_5$-avoidance argument, when ${\pi }_G(v_{ij},a_i)$ and ${\pi }_G(v_{cd},a_c)$ cross on the plane, our key idea is to align the corresponding color sequences $S_{ij}$ and $S_{cd}$ at the crossing objects, which have different colors. Then, by a simple case analysis, we can still show that either (i) $|{\pi }_G(v_{cd},a_i)|\le |{\pi }_G(v_{cd},a_c)|$ or (ii) $|{\pi }_G(v_{ij},a_c)|\le |{\pi }_G(v_{ij},a_i)|$ as in the case of pseudo-disks and get a contradiction. We note that the color alignment argument holds only when there are two colors (due to bipartiteness); it does not hold when there are three or more colors. Indeed, for the case of three colors, we have a quadratic conditional lower bound by Theorem 1, and the VC-dimension is unbounded.

For string graphs of bounded chromatic number and bounded diameter, we decompose the set system $(V,{\{N^r[v]\}}_{v\in V,r\ge 0})$ into set systems of different types, each type corresponds to a fixed sequence of (vertex) colors. Then, for each sequence of colors $S$, we define a notion of ball $B_S(v)$ that contains all vertices reachable from $v$ by paths whose vertex colors form a subsequence of $S$; the goal is then to bound the VC dimension of $(V,{\{B_S(v)\}}_{v\in V})$. Our key insight is that, by restricting the color sequences in the definition of $B_S(v)$ to be subsequences of $S$, we could apply our color alignment argument again. The case analysis is more delicate, but the underlying idea remains the same as in bipartite string graphs. The proof is given in Section 3.2.

Finally, in Section 3.3, we adapt the argument for string graphs of bounded chromatic number and bounded diameter to (possibly degenerate) line segments with few slopes. Here, the new issue is that the colors are not proper: the endpoints of an edge could share the same color. We get around this issue by exploiting the fact that objects are line segments. Roughly speaking, if two segments $s$ and $\tilde{s}$ of the same slope, say horizontal, intersect, then one of the neighbors of $s$ will intersect $\tilde{s}$ (or vice versa). This means we can align the color of a neighbor of $s$ with that of $\tilde{s}$, and hence the color alignment argument can be applied again.

In this section, we present an $O^{\ast }(n)$-time algorithm for testing whether the diameter of a 2D unit-square graph is at most $\mathrm{\Delta }$, for any given constant $\mathrm{\Delta }$. The precise time bound is $n{2}^{O(\sqrt{\log n\log \log n})}$, interestingly. All squares in this section are axis-aligned. Our result significantly extends Bringmann et al.’s near-linear algorithm for unit-square graphs [4], which worked only for $\mathrm{\Delta }=2$. It also significantly improves the $\tilde{O}(n^{7/4})$ time bound of Duraj, Konieczny, and Potępa’s algorithm [14] in the constant $\mathrm{\Delta }$ case; since Duraj et al.’s approach is based on distance VC-dimension, it does not seem possible to improve their time bound to near linear (the VC-dimension or shatter dimension for unit squares is at least 2 even for 1-neighborhoods!). Our new algorithm employs an unusual divide-and-conquer approach:

1. 1.

   Often in computational geometry, we divide based on (say) the median $x$- or $y$-coordinate, but in our new algorithm, we will divide based on coordinate values modulo 1.

2. 2.

   We will use a larger fan-out rather than dividing 2-way.

3. 3.

   We will repeatedly map input points to new points in a higher dimension (dependent on $\mathrm{\Delta }$), constructed in a nontrivial way, to enable orthogonal range searching techniques.

Even though the diameter problem may not at first seem amenable to divide-and-conquer (not being a “decomposable” problem), we show that a combination of these ideas is powerful enough to solve the problem efficiently for any constant $\mathrm{\Delta }$ (unlike the far more straightforward approach by Bringmann et al. for $\mathrm{\Delta }=2$).

For a point $p\in {ℝ}^2$, denote by $⟦p⟧$ the unit square centered at $p$. Let $x(p)$ and $y(p)$ denote the $x$- and $y$-coordinate of a point $p$ respectively. To keep the presentation simple, we assume that all coordinate values are distinct. It is straightforward to modify the algorithm below to handle cases when some values may be equal, just by being more careful about vs. $\le$ signs and open vs. closed intervals. (This is unlike our other results on axis-aligned line segments, where degeneracies can make a big difference.) We will solve the problem in a slightly more general setting for $\mathrm{\Delta }+1$ point sets $P_0,\mathrm{\dots },P_{\mathrm{\Delta }}$: testing whether all distances between $⟦p_0⟧$ and $⟦p_{\mathrm{\Delta }}⟧$ for $(p_0,p_{\mathrm{\Delta }})\in P_0\times P_{\mathrm{\Delta }}$ are exactly $\mathrm{\Delta }$ in the $(\mathrm{\Delta }+1)$-partite intersection graph of the unit squares centered at $P_0,\mathrm{\dots },P_{\mathrm{\Delta }}$, i.e., the subgraph of the intersection graph where we include an edge between $⟦p⟧$ and $⟦q⟧$ only when $p\in P_j$ and $q\in P_{j+1}$ for some $j\in \{0,\mathrm{\dots },\mathrm{\Delta }-1\}$. The original problem reduces to the case when $P_0,\mathrm{\dots },P_{\mathrm{\Delta }}$ are identical sets (or almost identical, if we want to ensure general position).

Build a uniform grid over ${ℝ}^2$ of unit side length. We first identify a special case which we can solve quickly. Specifically, suppose that the points $p_j\in P_j$ lie in a fixed grid cell for a fixed $j$, and points in $p_{j+1}\in P_{j+1}$ lie in a fixed neighboring grid cell, w.l.o.g., say, to its right; furthermore, suppose that all such points satisfy $x(p_j)mod1>\mu$ and . Then we already know that , and so it suffices to enforce only the constraint that . Consequently, we can proceed greedily: for each $p_0\in P_0$, we only need to find the lowest point in $P_j$ reachable from $p_0$, and for each $p_{\mathrm{\Delta }}\in P_{\mathrm{\Delta }}$, we only need to find the highest point in $P_{j+1}$ reachable from $p_{\mathrm{\Delta }}$ (or vice versa, depending on the position of neighboring cell), as explained in the lemma below: