We look forward to seeing you in-person in 3401 SC or online.
Abstract:
In SoCG 2022, Conroy and Toth presented several constructions of sparse,low-hop spanners in geometric intersection graphs, including an O(n log n)-size 3-hop spanner for n disks (or fat convex objects) in the plane, and an O(n log^2 n)-size 3-hop spanner for n axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can near-linear size be achieved for more general classes of intersection graphs?
We address both questions simultaneously, by presenting new constructions of constant-hop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an O(1)-hop spanner for arbitrary string graphs with O(n alpha_k(n)) size for any constant k, where alpha_k(n) denotes the k-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an O(1)-hop spanner for intersection graphs of d-dimensional fat objects with O(n alpha_k(n)) size for any constant k and d.
We also improve on some of Conroy and Toth's specific previous results, in either the number of hops or the size: we describe an O(n log n)-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an O(n log n)-size 3-hop spanner for axis-aligned rectangles in the plane.
Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings.
