Home | Bookmarks | Papers | Blog |

Sariel Har-Peled, and Eliot W. Robson.

The intersection graph induced by a set $\Disks$ of $n$ disks can be dense. It is thus natural to try and sparsify it, while preserving connectivity. Unfortunately, sparse graphs can always be made disconnected by removing a small number of vertices. In this work, we present a sparsification algorithm that maintains connectivity between two disks in the computed graph, if the original graph remains ``well-connected'' even after removing an arbitrary ``attack'' set $\BSet \subseteq \Disks$ from both graphs. Thus, the new sparse graph has similar reliability to the original disk graph, and can withstand catastrophic failure of nodes while still providing a connectivity guarantee for the remaining graph. The new graph has near linear complexity, and can be constructed in near-linear time. The algorithm extends to any collection of shapes in the plane with near linear union complexity.

PDF. : arXiv.

Last modified: Sat 2022-07-23 20:49:49 UTC 2022 by Sariel Har-Peled