An Investigation of Algorithms to Aesthetically Draw Cayley Graphs

Abbot, Alastair A. and Dinneen, Dr. Michael J. (2008) An Investigation of Algorithms to Aesthetically Draw Cayley Graphs. [Departmental Technical Report] (Unpublished)

[img] PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
488Kb

Abstract

Graph visualisation is an important field in Computer Science. The visualisation of groups in the form of Cayley graphs has applications in the layout of interconnected networks and mathematics. By using theoretical results from group theory, we present two algorithms that take as input a Cayley graph $(G,S)$ and draws it in a layout that highlights the symmetry of the group and is easily readable.

Item Type:Departmental Technical Report
Keywords:graph symmetry visualization, Cayley Graphs, nested drawing, radial drawing,
Classifications:Z Theory > Z.500 Representations
M Methods > M.400 Force-directed / Energy-based
M Methods > M.100 Algebraic
D Aesthetics > D.001 General
G Algorithms and Complexity > G.910 Symmetries
ID Code:812
Alternative Locations:http://www.cs.auckland.ac.nz/CDMTCS//researchreports/318mjd.pdf

Repository Staff Only: item control page

References

R. Fleischer and C. Hirsch: Graph Drawing and its Application, in: Drawing Graphs - Methods and Models, Lecture Notes in Computer Science, Vol. 2025, New York: Springer

M. Jünger and P. Mutzel: Graph Drawing Software, Berlin: Sringer, 2004

P. Eades and X. Lin: Spring algorithm and symmetry, in: Theoretical Computer Science, Vol 240 (2), pp. 379-405, 2000

J.A. Gallian: Contemporary Abstract Algebra, 5. ed., Boston: Houghton Mifflin, 2002

M.-C. Heydemann: Cayley Graphs and Interconnection Networks, in: Graph Symmetry - Algebraic Methods and Applications, Vol. 497, Mathematical and physical Sciences, G. Hahn and G. Sabidussi, Eds. Dordrecht: Kluwer, 1996, pp. 167-224

W.H. Campbell: Indexing Permutations, in: Journal of Computer Sciences in Colleges, Vol. 112 (1), pp. 296-300, 2004

D. Renault: Enumerating Planar Locally Finite Cayley Graphs, in: Geometriae Decicata, Vol. 112 (1), pp. 25-49, 2005

T. Kamada and S. Kawai: Automatic display of Network Structure for Human Understanding, in: Information Processing Letters, Vol. 31, pp. 7-15, 1989

M.J. Dinneen and P.R. Hafner: New results for the Degree/Diameter Problem, in: Networks, Vol. 24, pp. 359-367, 1994

A.T. White: Graphs of Groups on Surfaces - Interactions and Models, Amsterdam: Elsevier, 2001

A.D. Thomas and G.V. Wood: Group Tables, Kent: Shiv A Publ., 1980