Isomorphism testing and display of symmetries in dynamic trees

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(log2nlogm 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.

Date of Award	1995
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology