ylfink@water.waterloo.edu (ylfink) (10/18/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Friday, October 21, 1988
Mr. Krishna Gopinathan, a graduate student of this
department, will speak on ``Decomposing a Graph
Uniquely into Triconnected Components''.
TIME: 12:00 NOON
ROOM: MC 5158
ABSTRACT
An efficient algorithm to decompose a graph uniquely
into triconnected components is both theoretically
interesting and useful in a variety of applications.
It can be used for efficient planarity testing of
graphs and isomorphism of planar graphs, which are of
interest in such areas as printed circuit board design
and structural isomorphism of chemical compounds.
Further, it has applications in the analysis of
electric circuits and networks.
A triconnected graph is a graph which has no separation
pair, ie. no pair of vertices whose deletion would
disconnect the graph. There is a linear algorithm due
to Hopcroft and Tarjan which completely decomposes a
graph using its separation pairs. But this results in
final pieces which are not unique. So the algorithm
then undoes some of the splits in such a way as to
produce unique components.
We provide a characterization of the separation pairs
in the graph as ``good'' and ``bad'' in such a way that
using all the ``good'' separation pairs and no ``bad''
ones would provide a unique decomposition. We also
show that the splits being undone by the Hopcroft-
Tarjan algorithm are none other than those generated by
the separation pairs we have characterized as ``bad''.