Canonical representation of unordered rooted trees

This example shows a canonical (non-ambiguous) representation of a randomly generated unordered rooted tree. Reload to generate a new one. This is an improvement of a previous example.

Unordered rooted trees are trees (with a root) in which sibling order is not defined. Visualizing such trees often involves showing siblings in arbitrary order.

Serializations of unordered trees are often ordered, therefore, they are not necessarily equal to each other even if they represent the same unordered tree. A particular case is that of randomly generated trees.

If such serializations are fed into a tree layout algorithm, it can yield different representations of the same unordered tree, which is undesirable.

We perform a total ordering of the tree, based solely on topological features, which constrains an order-preserving tree layout algorithm to yield a single representation (barring other layout parameters). The total ordering is used to sort the tree before passing it to the layout algorithm. The method could also be applicable to some non-order-preserving layouts.

For an introduction on canonical representation of unordered trees, see Wright et al. 1986 (we still have to verify if our implementation yields the same results).

For an in-depth survey about tree drawing algorithms, see the chapter about tree drawing from the Handbook of Graph Drawing and Visualization (2013).