Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420897 | Discrete Applied Mathematics | 2007 | 16 Pages |
Abstract
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 nn-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 nn 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 [〈〈http://magma.maths.usyd.edu.au〉〉] 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
David Abelson, Seok-Hee Hong, D.E. Taylor,