maintaining a balanced spanning tree of a growing undirected graph
Every time you add a new vertex with an edge, you don't have options.
Every time you add a new edge, if the current distance to the root is bigger than the distance through the new edge, you remove the old edge in the old shortest path and add the new one. Otherwise, you just keep your tree unchanged. I think this way you get something very similar to a BFS tree in the sense that the levels of the tree will contain the same vertices and the distance from a vertex to the root will be the same as the distance in the BFS tree (and in the graph), but I don't know if that's enough to satisfy your "ideal balanced spanning tree" condition.