Sparsifying Disk Intersection Graphs for Reliable Connectivity
$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\Mh}[1]{#1}
\newcommand{\Disks}{\Mh{\mathcal{C}}}%
\newcommand{\BSet}{\Mh{B}}%
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
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