Robust Geometric Spanners

DOI10.1137/120874473zbMath1311.68105arXiv1204.4679OpenAlexW1988867024MaRDI QIDQ2862209

Vida Dujmović, Pat Morin, Prosenjit Bose, Michiel H. M. Smid

Publication date: 14 November 2013

Published in: SIAM Journal on Computing, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.4679

zbMATH Keywords

expansiontreewidthconnectivitygeometric spannersfault-tolerancespannershigh treewidthspanning-ratiostretch-factor

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Reliable Spanners for Metric Spaces ⋮ A spanner for the day after ⋮ Sometimes Reliable Spanners of Almost Linear Size. ⋮ Unnamed Item ⋮ Average stretch factor: how low does it go?

This page was built for publication: Robust Geometric Spanners