I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each step, I add to the graph either a "cross edge" or a "parent-child edge". Cross edges introduce no new nodes; they just connect two existing nodes. Parent-child edges introduce a new node, the child, and connect it to an existing node, the parent. Parent-child edges are in the spanning tree; cross-edges are not.
The problem is, the order in which these edges arrive is beyond my control, and if I just build the tree out of parent-child edges as they come, it can be very unbalanced.
Is there some algorithm that maintains a relatively balanced spanning tree of a growing graph, short of re-building the tree at each step with a breadth-first traversal?
Note that the standard google responses to terms like "balanced" "spanning" and "tree" seem to be binary trees and B-trees, neither of which apply. My tree nodes can have any number of children, not 2, and B-trees maintain balance by changing their adjacency lists. I'm not allowed to change the connectivity of the underlying graph.