Abstract
We describe data structures for maintaining a set of trees so that isomorphism testing for any two trees can be performed in O(1) time. Updates include inserting an edge to merge two trees or removing an edge to split a tree into two smaller trees. Each update can be performed in O(log²nlogm log*m) time, where n is the total size of trees involved and m is the number of updates performed so far. The space needed per update is O(logn logm log*m). We apply this result to display symmetries in dynamic free trees. A framework for dynamic symmetric drawing of free trees is developed, which supports the drawing of subtrees in an output-sensitive manner.