9.4 Multitrees

Recently George Furnas and Jeff Zacks have introduced a new structure for representing partly hierarchical information [Fur94], the multitree. Multitrees are directed acyclic graphs (DAGs) that have large, identifiable substructures that are trees.

Figure I.39 Sample Multitree http://www.sils.umich.edu/~furnas/HomePage.html

Obviously, reuse of hierarchy is not new. When teachers prepares a course, they might rearrange a large hierarchical syllabus to the particular needs of the course. If multiple professors prepare similar courses, they are all using the same hierarchical subtrees, although the overall structure (encompassing multiple professors) is not a tree. More precisely, in a multitree, the descendants of any node form a tree. As multitrees themselves are DAGs, and not trees, a node in the structure can have more than one parent. Multitrees can be perceived as unions of trees that share subtrees: Each user picks a set of subtrees of a large hierarchical resource and then places a customized hierarchy above those pieces for his/her own purposes.

As Furnas and Zacks note, genealogies, although frequently called "family trees", are in fact multitrees. Multitrees offer a natural notion of context (displaying ancestors) and content (displaying descendants), and are therefore very well suited for reusing hierarchical structure.