Fast detection and display of symmetry in outerplanar graphs

The automatic construction of good drawings of abstract graphs is a problem of practical importance. Symmetry appears as one of the main criteria for achieving goodness. Algorithms are developed for enumerating all planar axial and rotational symmetries of a biconnected outerplanar graph, and it is shown how to construct a drawing which simultaneously displays all these symmetries. These results are then expanded to obtain algorithms for the detection and display of outerplanar axial and rotational symmetry in the entire class of outerplanar graphs. All algorithms run in both time and space which are linear in the size of the graph, and hence are optimal to within a constant factor.