Article ID Journal Published Year Pages File Type
420897 Discrete Applied Mathematics 2007 16 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,