Dynamic subgraph connectivity with geometric applications

Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph G = (V, E) and a subset of vertices S ⊆ V, to support insertions and deletions in S and connectivity queries (are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, Õ(|E|^4ω/(3ω+3)) = O(|E|^0.94) amortized update time, and Õ(|E|^1/3) query time, where ω is the matrix multiplication exponent and Õ hides polylogarithmic factors.