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. [ABSTRACT FROM AUTHOR]