Fast detection and display of symmetry in trees - Manning, Joseph; Atallah, Mikhail J. (Congressus Numerantium, 1988)
The automatic construction of good drawings of abstract graphs is a problem of practical importance. Displaying symmetry appears as one of the main criteria for achieving goodness. An expression is obtained for the maximum number of axial symmetries of a tree which can be simultaneously displayed in a single drawing, and an algorithm is presented for constructing such a maximally-symmetric drawing. Similar results are also obtained for rotational symmetries in trees. The algorithms run in time which is linear in the size of the tree, and hence are optimal.