Kevin Buchin, Sariel Har-Peled, Dániel Oláh

Research output: Contribution to journalArticlepeer-review


Reliable (Euclidean) spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(n log n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1 + ε)-spanners, for n points in Rd, are known, where the resulting graph has O(n log n loglog6n) edges. Here, we show randomized constructions of smaller size Euclidean spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical – replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in Rd with O(n loglog2n logloglog n) edges.

Original languageEnglish (US)
Pages (from-to)178-196
Number of pages19
JournalJournal of Computational Geometry
Issue number1
StatePublished - 2022

ASJC Scopus subject areas

  • Geometry and Topology
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'SOMETIMES RELIABLE SPANNERS OF ALMOST LINEAR SIZE'. Together they form a unique fingerprint.

Cite this