Is there an online-algorithm to keep track of components in a changing undirected graph? Problem

I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected components of this graph.

Properties

Additional properties are that no two components will ever be reconnected. Obviously, the graph can have cycles to an arbitrary amount (otherwise the solution would be trivial).
If an edge $e$ does not contain a node $n$, it will never adopt that node. However, if $n \in e$, it can change to $n \notin e$.

Approaches

I have two possible approaches so far, but as you will see they are horrible:

Slow state-less

I can search (dfs/bfs) the graph starting from the modified element(s) every time. This conserves space, but is slow as we have O(n+m) for each modification.

Stateful fast(-er) (?) approach

I can store all possible paths for each node to all possible nodes, but if I see it correctly, this will take O(n^4) memory. But I am not sure how the runtime improvement is (if there is one at all, because I have to keep the information up-to-day for every node in the same component).

Question

Do you have any pointers, how I can learn more about that problem or perhaps some algorithms I can build on?

Note

If there is a vast improvement in runtime/memory I could live with a non-optimal solution that sometimes says two components are one, but of course I would prefer an optimal solution.
There are several data structures that support edge insertions, edge deletions, and connectivity queries (Are these two vertices in the same connected component?) in polylogarithmic time.


Monika R. Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  Journal of the ACM 46(4):502—516, 1999.
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM 48(4):723—760, 2001.
Mikkel Thorup.  Near-optimal fully-dynamic graph connectivity.  Proc. 32nd STOC 343—350, 2000.