Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion
This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.

You could also try Bhadra &amp; Ferreira, they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.