Center for Global Studies

View Full Calendar

Zhengcheng Huang "Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size"

Event Type
Illinois Computer Science
3401 Siebel Center for Computer Science
wifi event
Feb 27, 2023   11:00 am  
Zhengcheng Huang, University of Illinois
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

We look forward to seeing you in-person in 3401 SC or online


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.


link for robots only