Symmetric Drawings of General Graphs in Three Dimensions


David Abelson, Seok-Hee Hong and Don E. Taylor, Geometric Automorphism Groups of Graphs, Discrete Applied Mathematics, 155(17), pp. 2211-2226, 2007, Elsevier.

Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an n-geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in n dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups.



For viewing large drawings, pls click the drawings.