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, Irvine, CA, USA , pp. 86-97 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_9).

Full text not available from this repository.

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 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
ID Code:267

Repository Staff Only: item control page

References

D. Abelson, S. Hong and D.E. Taylor, A Group-Theoretic Method for Drawing Graphs Symmetrically, Technical Report IT-IVG-2002-01, School of Information Technologies, The University of Sydney, 2002.

C. Buchheim and M. Jünger, Detecting Symmetries by Branch and Cut, Graph Drawing 2001, Lecture Notes in Computer Science LNCS 2265, pp. 178-188, Springer Verlag, 2002.

P. Eades and X. Lin, Spring Algorithms and Symmetries, Theoretical Computer Science, 240, pp. 379-405, 2000.

H. Fraysseix, An Heuristic for Graph Symmetry Detection, Graph Drawing '99, Lecture Notes in Computer Science 1731, pp. 276-285, Springer Verlag, 1999.

S.Hong, P. Eades and S. Lee, An Algorithm for Finding Geomertic Automorphisms in Planar Graphs, Algorithms and Computation, Lecture Notes in Computer Science 1533, pp. 277-286, Springer Verlag, 1998.

S.Hong, Drawing Graphs Symmetrically in Three Dimensions, Graph Drawing 2001, Lecture Notes in Computer Science 2265, pp. 189-204, Springer Verlag, 2002.

S.Hong and P. Eades, Drawing Planar Graphs Symmetrically IV: Disconnected Graphs, Technical Report CS-IVG-2001-03, Basser Department of Computer Science, The University of Sydney, 2001.

J. Manning, Geometric Symmetry in Graphs, Ph.D. Thesis, Purdue Univ., 1990.

Groups & Graphs, http://130.179.24.217/G&G/G&G.html.

W. Ledermann, Introduction to Group Theory, Longman, 1973.

Magma, http://magma.maths.usyd.edu.au.

nauty, http://cs.anu.edu.au/~bdm/nauty.

Rome test suite ALF/CU, http://www.dia.uniroma3.it/~gdt.