Sparse bounded hop-spanners for geometric intersection graphs

DOI10.4230/LIPICS.SOCG.2025.17MaRDI QIDQ7312657zbMATH OpenFDO

Authors Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2025.17

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A semi-algebraic version of Zarankiewicz's problem
• Almost tight upper bounds for vertical decompositions in four dimensions
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximate nearest neighbor queries revisited
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Constant-hop spanners for more geometric intersection graphs, with even smaller size
• Dynamic data structures for fat objects and their applications
• Dynamic Subgraph Connectivity with Geometric Applications
• Geometric Spanner Networks
• Hop-spanners for geometric intersection graphs
• scientific article; zbMATH DE number 3907247 (Why is no real title available?)
• scientific article; zbMATH DE number 1943961 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Improved bounds for the union of locally fat objects in the plane
• Intersection queries for flat semi-algebraic objects in three dimensions and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Multilevel polynomial partitions and simplified range searching
• On range searching with semialgebraic sets
• On sparse spanners of weighted graphs
• On the Erdős distinct distances problem in the plane
• On the number of incidences when avoiding an induced biclique in geometric settings
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planar Hop Spanners for Unit Disk Graphs
• Plane hop spanners for unit disk graphs: simpler and better
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quasi-optimal range searching in spaces of finite VC-dimension
• Realistic input models for geometric algorithms
• Reporting points in halfspaces
• Spanners for geometric intersection graphs with applications
• Sparse hop spanners for unit disk graphs
• The constant of point-line incidence constructions
• Turán-type results for intersection graphs of boxes
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
• Zarankiewicz's problem for semilinear hypergraphs

This page was built for publication: Sparse bounded hop-spanners for geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312657)