Tuesday, May 17, 2016 2:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Characterizing planarity and graphicness by linear equations
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Given
a
graph
G
on
n
vertices
we
construct
a
system
of
O(n3)
equations
in
O(n2)
variables
that
has
a
solution
over
the
two-element
eld
if
and
only
if
the
graph
is
planar.
In
fact,
we
will
solve
the
more
general
problem
of
determining
whether
a
given
binary
matroid
is
graphic.
This
is
joint
work
with
Bert
Gerards.