__COMPUTER SCIENCE SEMINAR
__

__ __

**Toroidal and projective-planar graphs avoiding K3,3’s:**

**detection algorithms and structure.**

** **

**D****r. Andrei Gagarin**

** **

**Friday
February 2**^{ND}, 2007 at 2:30 p.m.

** **

**Carnegie
Hall - Room 113**

** **

__Abstract:__ Graphs are used to model many
problems that involve connections between**
**objects or
relations between people. Detection of graphs embeddable on topological surfaces
is one of the classical fundamental problems in combinatorics and graph theory.
It is related to VLSI design and can be used to model interaction of particles
in physics. The plane is a basic topological surface which is equivalent to the
sphere. The torus and projective plane are the topological surfaces closest to
the plane. The torus can be imagined as the sphere with an attached handle or as
a doughnut. By Kuratowski’s theorem, a non-planar graph contains a subdivision
of K5 or K3,3. We consider graphs containing a subdivision of
K5 and provide a linear-time algorithm that either
checks the toroidality and/or projective-planarity of these graphs, or finds a
subdivision of K3,3 (joint work with William Kocay, University of
Manitoba).**
**We refine
the algorithmic results and show the structure of toroidal and
projectiveplanar**
**graphs with
no K3,3’s in terms of two-pole planar networks substituted
for the edges of canonically defined non-planar cores (joint work with Pierre
Leroux and Gilbert**
**Labelle,
Universit´e du Qu´ebec `a Montr´eal). The algorithmic results are also used to
prove Kuratowski-type theorems for toroidal graphs with no K3,3’s (joint work with Wendy Myrvold,
University of
Victoria).

__Biography:__ Dr. Andrei Gagarin received a Ph.D.
in Computer Science from the University of Manitoba in 2003. He did his undergraduate
studies and received a M.Sc. from Belarus State
University (Minsk, Belarus) and received a M.Sc. degree from
National Polytechnic Institute and Universit´e Joseph Fourier (Grenoble, France). In 2003-2006 he was a
post-doctoral research fellow in combinatorics and bioinformatics at Universit´e
du Qu´ebec `a Montr´eal. Currently he works as an Assistant Professor in the
School of Computer Science at Acadia University. His main research interests
are in graph theory, combinatorics, statistical analysis, clustering and data
processing, practical algorithms and their
applications.

__ALL
COMPUTER SCIENCE GRADUATE STUDENTS ARE REQUIRED TO
ATTEND__