Sparsifying disk intersection graphs for reliable connectivity

DOI10.57717/CGT.V3I1.66MaRDI QIDQ7033707zbMATH OpenFDO

Authors Eliot W. Robson, Sariel Har-Peled

Publication date 3 February 2025

Published in CGT. Computing in Geometry and Topology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.57717/CGT.V3I1.66

zbMATH Keywords

expandersintersection graphsreliabilityspanners

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites work

• A spanner for the day after
• Applications of random sampling in computational geometry. II
• Computational geometry. Algorithms and applications.
• scientific article; zbMATH DE number 1220053 (Why is no real title available?)
• Improved bounds for the union of locally fat objects in the plane
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Sometimes Reliable Spanners of Almost Linear Size.

This page was built for publication: Sparsifying disk intersection graphs for reliable connectivity

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