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/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 a combination of several simple ideas. Our method requires Õ(|E| ^4ω/(3ω+3)) = O(|E|^0.94) amortized update time, and Õ(|E|^1/3) query time, after Õ(|E| ^{(5ω+1)/(3ω+3)}) preprocessing time, where ω is the matrix multiplication exponent and Õ hides polylogarithmic factors.