I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right.
I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation).
From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.
I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup (2001; pdf). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario?