Home Bookmarks Papers Blog

# Sparsifying Disk Intersection Graphs for Reliable Connectivity

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.