Spring algorithms and symmetry

Spring algorithms are regarded as effective tools for visualizing undirecte d graphs. One major feature of applying spring algorithms is to display sym metric properties of graphs. This feature has been confirmed by numerous ex periments. Ln this paper, firstly we formalize the concepts of graph symmet ries in terms of "reflectional" and "rotational" automorphisms; and charact erize the types of symmetries, which can be displayed simultaneously by a g raph layout, in terms of "geometric" automorphism groups. We show that our formalization is complete. Secondly, we provide general theoretical evidenc e of why many spring algorithms can display graph symmetry. Finally, the st rength of our general theorem is demonstrated from its application to sever al existing spring algorithms. (C) 2000 Elsevier Science B.V. All rights re served.