Title: Department of Computer Science Seminar
Date: Wednesday, March 29, 2000
Time: 4:00 pm to 5:00 pm
Venue: Room N101, CSIT Building [108]
Speaker: Dr Seokhee Hong (Dept. of Computer Science 
         & Software Engineering, University of Newcastle)
Description: "Algorithms for Finding Planar Geometric Automorphisms 
                         in Planar Graphs"


                        Abstract

Graph drawing is the construction of geometric
representations of graphs in two or three dimensions.
It has many applications such as information visualization,
VLSI, software visualization, software engineering,
biology and chemistry.

Symmetry is the most important aesthetic criterion
for graph drawing. It clearly reveals the structure 
of an abstract graph. Also, symmetric drawing 
enables us to understand how the entire graph is 
built up from smaller isomorphic subgraphs.

The problem of determining whether a graph
can be drawn symmetrically is NP-complete in general.
However, the problem can be solved in polynomial time
for several restricted classes of graphs, 
and this talk covers two such classes.

We define planar geometric automorphism which can be
displayed as a symmetry of a planar drawing of a graph.
We also define upward planar automorphism which can be
displayed as a symmetry of a upward planar drawing of a graph.

Based on these models, we present a linear time algorithm
for finding upward planar automorphisms in 
series parallel digraphs. Further, 
we present a polynomial time algorithm
for finding planar geometric automorphisms in planar graphs.



 
URL: http://cs.anu.edu.au/lib/seminars/seminars00/dept2000032