2026-08-14T17:23:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17873 2024-03-06T11:00:35Z ddc:004 open_access

Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size Chan, Timothy M. Huang, Zhengcheng Hop spanners geometric intersection graphs string graphs fat objects separators shallow cuttings In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an O(nlog n)-size 3-hop spanner for n disks (or fat convex objects) in the plane, and an O(nlog² 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α_k(n)) size for any constant k, where α_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α_k(n)) size for any constant k and d. We also improve on some of Conroy and Tóth’s specific previous results, in either the number of hops or the size: we describe an O(nlog n)-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an O(nlog 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Zhengcheng Huang 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.23 urn:nbn:de:0030-drops-178738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode