  This paper considers fully dynamic graph algorithms with both faster worst
case update time and sublinear space. The fully dynamic graph connectivity
problem is the following: given a graph on a fixed set of n nodes, process an
online sequence of edge insertions, edge deletions, and queries of the form "Is
there a path between nodes a and b?" In 2013, the first data structure was
presented with worst case time per operation which was polylogarithmic in n. In
this paper, we shave off a factor of log n from that time, to O(log^4 n) per
update. For sequences which are polynomial in length, our algorithm answers
queries in O(log n/\log\log n) time correctly with high probability and using
O(n \log^2 n) words (of size log n). This matches the amount of space used by
the most space-efficient graph connectivity streaming algorithm. We also show
that 2-edge connectivity can be maintained using O(n log^2 n) words with an
amortized update time of O(log^6 n).

Data Structures and Algorithms