Brendan McKay (ANU, Australia)
Hubert de Fraysseix (EHESS, France)
Visualization of Graph Symmetries through Factorial Analysis
Given a graph G with n
vertices, we define an Euclidean semi-distance d on its vertex set
invariant under the automorphism group of the graph. An automorphism of
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).
Jozef Siran (Slovak University of Technology, Slovakia)
Symmetries of Non-Planar Graphs Embedded in Compact Surfaces
It is well known that
the only finite groups that act on a 2-dimensional sphere as groups of
orientation-preserving isometries are Zn, Dn,
S4, or A5. If the action is allowed
to reverse orientation, then the list also includes direct products of
the above groups with Z2. 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.
Hsu-Chun Yen (National Taiwan University, Taiwan)
Near Symmetry in Graph Drawings
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.
Joseph Manning (University College Cork, Ireland)
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.
Xuemin Lin (UNSW, Australia)
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.
Peter Eades (University of Newcastle, Australia)
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.
Seokhee Hong (University of Newcastle, Australia)
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.
William Unger (University of Sydney, Australia)
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.