COMPUTER SCIENCE SEMINAR
Toroidal and projective-planar graphs avoiding K3,3’s:
detection algorithms and structure.
Dr. Andrei Gagarin
Friday February 2ND, 2007 at 2:30 p.m.
Carnegie Hall - Room 113
Abstract: Graphs are used to model many
problems that involve connections between
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
the algorithmic results and show the structure of toroidal and
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
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,
Biography: Dr. Andrei Gagarin received a Ph.D.
in Computer Science from the
ALL COMPUTER SCIENCE GRADUATE STUDENTS ARE REQUIRED TO ATTEND