English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In SoCG 2022, Conroy and T\'oth presented several constructions of sparse,low-hop spanners in geometric intersection graphs, including an $O(n\logn)$-size 3-hop spanner for $n$ disks (or fat convex objects) in the plane, andan $O(n\log^2 n)$-size 3-hop spanner for $n$ axis-aligned rectangles in theplane. Their work left open two major questions: (i) can the size be madecloser to linear by allowing larger constant stretch? and (ii) can near-linearsize be achieved for more general classes of intersection graphs?  We address both questions simultaneously, by presenting new constructions ofconstant-hop spanners that have almost linear size and that hold for a muchlarger class of intersection graphs. More precisely, we prove the existence ofan $O(1)$-hop spanner for arbitrary string graphs with $O(n\alpha_k(n))$ sizefor any constant $k$, where $\alpha_k(n)$ denotes the $k$-th function in theinverse Ackermann hierarchy. We similarly prove the existence of an $O(1)$-hopspanner 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 T\'oth's specific previous results, ineither the number of hops or the size: we describe an $O(n\log n)$-size 2-hopspanner for disks (or more generally objects with linear union complexity) inthe plane, and an $O(n\log n)$-size 3-hop spanner for axis-aligned rectanglesin the plane.  Our proofs are all simple, using separator theorems, recursion, shiftedquadtrees, and shallow cuttings.

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