Show HN: Dynamic graph connectivity data structure

EDIT: If you want an example application, suppose you have a physics simulation with a bunch of connected rigid bodies. You would like to be able to quickly test if two boxes are connected by links to the same body or to detect if after breaking a joint the resulting body becomes disconnected into two different pieces. Using a data structure like this would be faster than brute force searching over the graph of all bodies every time you change a link by connecting/disconnecting two bodies.

The main drawback has typically been that whilst they can be made to be incremental (e.g. the addition of vertices or edges) quite easily, they don't retain enough information to be made fully dynamic (addition AND removal of vertices and edges) without prohibitively increasing the space complexity required.

This data-structure, however, has particularly good time/space properties that make it interesting to anyone working on large-scale graph-analytical problems with a temporal component.