Thursday, May 11, 2017 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Recognizing
Circle
Graphs
| Speaker: | Edward Lee |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract:
A
circle
graph
is
the
intersection
graph
of
chords
on
a
circle.
There
is
a
correspondence
between
bipartite
circle
graphs
and
planar
graphs,
and
hence
every
characterization
for
the
class
of
circle
graphs
gives
a
characterization
for
the
class
of
planar
graphs.
Given
a
graph,
Naji
describes
a
system
of
linear
equations
whose
solvability
determines
whether
or
not
the
graph
is
a
circle
graph.
We
will
sketch
a
new
proof
of
this
beautiful
theorem
which
is
considerably
simpler
than
the
existing
proofs
due
to
Naji,
Gasse,
and
Traldi.
This
is
joint
work
with
Jim
Geelen.