COMPUTER SCIENCE SEMINAR

 

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

detection algorithms and structure.

 

Dr. 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