A Group-Theoretic Method for Drawing Graphs Symmetrically

Abelson, David and Hong, Seok-Hee and Donald E., Taylor (2002) A Group-Theoretic Method for Drawing Graphs Symmetrically. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 86-97(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_9).

Full text not available from this repository.


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 a n-geometric 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 graph. We implement the algorithm using Magma [11] and the experimental results shows that our approach is very efficient in practice. We also present a drawing algorithm to display a 2- or 3-geometric automorphism group.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_9
Classifications: Z Theory > Z.001 General
G Algorithms and Complexity > G.910 Symmetries
P Styles > P.780 Symmetric
URI: http://gdea.informatik.uni-koeln.de/id/eprint/267

Actions (login required)

View Item View Item