Abstract of Invited Talks

   Given a graph G with n vertices, we define an Euclidean semi-distance d on its vertex set V, invariant under the automorphism group of the graph. An automorphism of G thus induces an isometry of (V,d). We prove that the converse is also true: a bijection of V is an automorphism of G if and only if it is an isometry of (V,d). 
   Using a diagonalization of the inner product matrix D defined by d we embed the set V in R^n-1 (in the general case). 
   A bijection of V is an isometry if and only if it is an isometry in all the proper subspaces of  D. The automorphism group of G is hence the product of the isometry groups of the proper subspaces. So there is a strong relationship between the eigenvalues of  D and the possible automorphism groups. 
   Obviously, we need to consider only proper spaces with a non trivial isometry of V. Notice that if Aut(G) is irreducible, only one proper space remains. 
   It is also intuitive that two special kind of proper spaces will be of great interest: proper spaces of low dimension (essentially 1 or 2) and proper spaces associated with the highest eigenvalues (principal inertial spaces). 
   We give some hints on symmetry visualizations through examples. 

   It is well known that the only finite groups that act on a 2-dimensional sphere as groups of orientation-preserving isometries are  Z_n, D_n, A₄,  S₄, or A₅. If the action is allowed to reverse orientation, then the list also includes direct products of the above groups with Z₂. On the other hand, any finite group G generated by two elements one of which is an involution (in particular, any finite simple group) acts on some connected compact orientable surface S as a group of orientation-preserving isometries. This raises the question of visualising the action of G on S in 2- or 3-dimensional drawings. 
   An action of a finite group G on a surface S is best represented by a map, that is, a graph cellularly embedded in S, such that G  is a subgroup of the automorphism group of the map. In the talk we will discuss possibilities and limitations of visualising actions of  G on S by 2- and 3-dimensional drawings of the corresponding (non-planar) graphs embedded in S. This is of particular interest when G  is the map automorphism group of a  regular   map -- that is, a map whose automorphism group is transitive on darts. Most of such groups turn out to be finite quotients of the hyperbolic triangle groups T(2,m,n), 1/m + 1/n  < 1/2, that act on a hyperbolic plane, leaving invariant a tessellation of m-gons, n of which meet at each vertex. Links to hyperbolic geometry will be mentioned as well. 

   Among various aesthetics investigated in the literature, "symmetry" has received much attention recently. As a symmetric graph can be decomposed into a number of isomorphic subgraphs, only a portion of the graph, together with the symmetry information, is sufficient to define the original graph. In this way, symmetric graphs can often be represented in a more succinct fashion than their asymmetric counterparts. In reality, however, we often have to lower our expectations by allowing imperfection while considering the so-called "nearly symmetric" drawings of graphs. To draw a graph in a nearly symmetric fashion, a good starting point might be to draw its symmetric subgraph as large as possible first, and then add the remaining nodes and edges to the drawing.
   We address the problem of computing a maximum (axially and rotationally) symmetric graph H from G by a number of basic graph operations. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Approximation algorithms and their analysis are also given for some of the intractable cases.   We also investigate the issue of finding a sequence of operations that leads to the symmetric graph, and see how such information can be used to give a nearly symmetric display of an originally asymmetric graph. 

   This talk begins with a discussion of the motivations, definitions, and complexity of symmetric graph drawing, together with some experimental statistical data on the occurrence of symmetry.  It goes on to review certain solved problems in this area, including optimal algorithms for the detection and display of symmetry in trees and outerplanar graphs, and a new algorithm for plane graphs. Finally, some open problems are presented and discussed.

   Spring algorithms are regarded as effective tools for visualizing undirected graphs.  One major feature of applying spring algorithms is to display symmetric properties of graphs. This feature has been confirmed by numerous experiments. 
   In this talk, firstly we formalize the concepts of graph symmetries in terms of "reflectional" and "rotational" automorphisms; and characterize the types of symmetries, which can be displayed simultaneously by a graph layout,  in terms of "geometric" automorphism groups.  Secondly, we provide general theoretical evidence of why many spring algorithms can display graph symmetry.
 

    In this talk we describe how to draw a planar graph as symmetrically as possible.  The method is made up of several algorithms, depending on the connectivity of the input graph. Each algorithm works in polynomial time.  The output in each case is a straightline planar drawing.

   Symmetry in three dimensions is much richer than that of two dimensions.   In this talk we extend symmetric graph drawing into three dimensions.  First, we suggest a model for drawing trees symmetrically in three dimensions. Based on this model, we describe how to draw trees as symmetrically as possible in three dimensions.

   The computer algebra system MAGMA supports computation in a wide variety of algebraic structures, including groups and graphs. A particular strength of MAGMA is allowing easy transfer from one algebraic structure to another within a single environment. For instance, from a graph, MAGMA can get its automorphism group and then explore that. This talk will be an introduction to MAGMA, relating particularly to graphs, groups and their interactions.