Speaker: Kevin Cheung, University of Waterloo 
Time:    Friday, March 14, 10:00 a.m.
Place:   room: SITE-1010 (note room), University of Ottawa
Title:   On recognizing (2k+1)-edge-connected
         (2k+1)-regular bicritical graphs

In 1995, Dillencourt and Smith gave a linear-time
algorithm for testing if a 3-dimensional trivalent
polytope is combinatorially equivalent to one that
is inscribed in the sphere.  It can be shown that
one part of their algorithm determines if a
non-bipartite 3-connected 3-regular planar graph
is bicritical.  (A graph G=(V,E) is bicritical if
G-u-v has a perfect matching for every pair of
vertices u and v.)

In this talk, I will show a generalization of
their ideas and describe an O(r^2 |V|log(|V|/r))
algorithm that recognizes r-edge-connected
r-regular bicritical graphs where r is odd and at
least 3.  For recognizing bicritical graphs in
general, the O(|V||E|) algorithm by Lou and Zhong
(2001) has the best known time-complexity bound.