Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
Sujoy Bhore Timothy M. Chan Zhengcheng Huang Shakhar Smorodinsky Csaba D. Tóth · 2025
Read Sparse Bounded Hop-Spanners for Geometric Intersection Graphs by Sujoy Bhore Timothy M. Chan Zhengcheng Huang Shakhar Smorodinsky Csaba D. Tóth (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05861.txt.
Introduction
Sujoy Bhore and co-authors study shortcut networks for shape graphs in a 2025 geometry paper. When shapes overlap, their intersection graph can be huge, and a spanner is a sparse stand-in where trips take only a few hops. The team tightens size bounds for two-hop and three-hop spanners across many shape families.
For balls in space they give a leaner two-hop construction, and for fat boxes a near-linear one. Broad curved objects admit small three-hop spanners tied to their description complexity. Matching lower bounds, including one for tetrahedra, show the limits are close to tight. The results map what sparsity geometry allows.
Catalog record
| CREATOR | Sujoy Bhore Timothy M. Chan Zhengcheng Huang Shakhar Smorodinsky Csaba D. Tóth |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-05861
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs Sujoy Bhore Timothy M. Chan Zhengcheng Huang Shakhar Smorodinsky Csaba D. Tóth Abstract We present new results on 2 2 - and 3 3 -hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2 2 - and 3 3 -hop spanners for many geometric intersection graphs in ℝ d \mathbb{R}^{d} . For example, we show that the intersection graph of n n balls in ℝ d \mathbb{R}^{d} admits a 2 2 -hop spanner of size O ∗ ( n 3 2 − 1 2 ( 2 ⌊ d / 2 ⌋ + 1 ) ) O^{*}\left(n^{\frac{3}{2}-\frac{1}{2(2\lfloor d/2\rfloor+1)}}\right) and the intersection graph of n n fat axis-parallel boxes in ℝ d \mathbb{R}^{d} admits a 2 2 -hop spanner of size O ( n log d + 1 n ) O(n\log^{d+1}n) . Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ d \mathbb{R}^{d} admits a 3 3 -hop spanner of size O ∗ ( n 3 2 − 1 2 ( 2 D − 1 ) ) O^{*}\left(n^{\frac{3}{2}-\frac{1}{2(2D-1)}}\right) , where D D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ 3 \mathbb{R}^{3} ), we provide a lower bound of Ω ( n 4 3 ) \Omega(n^{\frac{4}{3}}) . For 3 3 -hop and axis-parallel boxes in ℝ d \mathbb{R}^{d} , we provide the upper bound O ( n log d − 1 n ) O(n\log^{d-1}n) and lower bound Ω ( n ( log n log log n ) d − 2 ) \Omega\left(n(\frac{\log n}{\log\log n})^{d-2}\right) . 1 Introduction A spanner of a graph G is a subgraph G^{\prime} that approximately preserves the distances between pairs of vertices in G . More formally, let G=(V,E) be a simple graph. A spanning subgraph G^{\prime}=(V,E^{\prime}) is called a t -spanner for G if for every two vertices x,y\in V d_{G^{\prime}}(x,y)\leq t\cdot d_{G}(x,y) where d_{G}(x,y) denotes the shortest path distance between x and y in G . Here, t\geq 1 is a constant called the stretch factor (or stretch for short). Spanners are an important concept in graph theory and computer science, particularly in the context of geometric intersection graphs, where vertices represent geometric objects (such as approximate location, e.g., disks, rectangles) and edges represent intersections between these objects. The ability to construct spanners for geometric intersection graphs with fewer edges is crucial because it enables efficient algorithms for problems such as shortest path computation, network design, and routing while maintaining proximity to the original geometric distances. By using spanners, one can often reduce the complexity of geometric problems without sacrificing the quality of the solution (see, e.g., [ GNS16 , Li03 , MM17 , NS07 , Raj02 ] ). The following theorem is a cornerstone in the theory of spanners for general graphs: Theorem 1.1 ( [ ADD+93 ] ) . Let G=(V,E) be a simple undirected graph on n vertices. Let t\geq 1 be a fixed integer parameter. Then G contains a (2t-1) -spanner G^{\prime} with O(n^{1+\frac{1}{t}}) edges. Note that the above theorem is non-trivial only for t\geq 2 or stretch factor at least 3 . Indeed, one cannot hope to obtain a 2 -spanner with o(n^{2}) edges in general as is exemplified by the complete bi-partite graph K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil} . The general bound O(n^{1+\frac{1}{t}}) is conjectured to be optimal due to the Erdős Girth Conjecture [ Erd64 ] , and the spanner G^{\prime} of this size can be computed by a greedy algorithm. It would be interesting to ask what families of graphs admit 2-spanners with o(n^{2}) edges or 3 -spanners with o(n^{3/2}) edges. The intersection graph of a set system (X,\mathcal{F}) is a graph G=(\mathcal{F},E) , where the vertices correspond to the sets in \mathcal{F} , and there is an edge between sets A,B\in\mathcal{F} if and only if A\cap B\neq\emptyset . Every edge has unit weight. For geometric intersection graphs, t -spanners are also called t -hop spanners to emphasize the use of hop distance. In this paper, our goal is to obtain hop spanners for geometric intersection graphs that are smaller than guaranteed by Theorem 1.1 . Previous work on spanners in intersection graphs. Initial work on spanners for geometric intersection graphs was motivated by wireless communication, and was limited to unit disk graphs in the plane. In this setting, spanners for weighted graphs were also considered, where the weight of an edge is the distance between the disk centers [ FK12 , GGH+05 , GZ05 ] . Recent work focused on hop spanners for unit disk graphs [ Bin20 , CCV10 , DGT22 ] , and intersection graphs of other geometric objects (including string graphs) [ CH23 , CT23 ] . Most previous bounds are constrained to objects in the plane. Chan and Huang [ CH23 ] use shallow cuttings to show that any family of n objects, with union complexity bounded by \mathcal{U}(n) , admits a 2 -hop spanner of size O(\mathcal{U}(n)\log n) . This yields an O(n\log n) bound for disks or pseudodisks in the plane [ KLPS86 ] ; n\log n\cdot 2^{O(\log^{*}n)} for fat objects of constant algebraic description complexity [ AdBES14 ] , and in particular O(n\log n\log^{*}n) for fat triangles in the plane [ AdBES14 ] . Lower bounds can be derived from constructions for geometric intersection graphs with girth 2t+1 , as a t -spanner contains the entire graph [ BCS+21 , Dav21 , TZ21 ] . In particular, Davies [ Dav21 ] constructed families of axis-aligned boxes in \mathbb{R}^{3} whose intersection graph has unbounded girth and \omega(n) edges. The boxes in Davies’ construction project to squares in the xy -plane, so they can be lifted to hypercubes in \mathbb{R}^{4} with the same intersection pattern. See Table 1 for a list of known results. Hops Objects Dim. Upper Bounds Lower Bounds Ref. 2 unit disks 2 O(n) [ CT23 ] translates of a convex body 2 O(n) [ CT23 ] axis-aligned fat rectangles 2 O(n\log n) \Omega(n\frac{\log n}{\log\log n}) [ CT23 ] disks of arbitrary radii ( \ast ) 2 O(n\log n) \Omega(n\frac{\log n}{\log\log n}) [ CH23 , CT23 ] general fat objects ( \ast\ast ) 2 n\log n\cdot 2^{O(\log^{*}n)} \Omega(n\frac{\log n}{\log\log n}) [ CH23 , CT23 ] 3 general fat objects d\geq 2 O(n\log n) [ CH23 ] axis-aligned rectangles 2 O(n\log n) [ CH23 ] strings 2 O(n\log^{3}n) [ CH23 ] O_{k}(1) strings 2 O(n\alpha_{k}(n)) [ CH23 ] O(1) axis-aligned boxes d\geq 3 \omega(n) [ Dav21 ] O(1) axis-aligned hypercubes d\geq 4 O(n\alpha_{k}(n)) \omega(n) [ CH23 , Dav21 ] O_{d,k}(1) general fat objects d O(n\alpha_{k}(n)) [ CH23 ] Table 1: Summary of previously known results. The trivial lower bound in each case is \Omega(n) . The upper bound in ( \ast ) generalizes to O(\mathcal{U}(n)\log n) for objects with union complexity \mathcal{U}(.) ; and the lower bound holds for homothets of any convex body in the plane. The upper bound in ( \ast\ast ) holds for fat objects of constant algebraic description complexity. The function \alpha_{k}(.) denotes the k -th function in the inverse Ackermann hierarchy: \alpha_{0}(n)=n/2