Recognizing Circle Graphs

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.

Date
Jun 15, 2017 4:20 PM — 4:45 PM
Location
Ryerson University
350 Victoria St., Toronto, ON M5B 2K3