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.
Bouchet characterized the class of circle graphs as the set of graphs which exclude the 5-wheel, the 7-wheel, and the fundamental graph of the Fano plane as vertex minors. This characterization is akin to Kuratowski’s excluded minorcharacterization of planar graphs, and one can indeed obtain Kuratowski’s result from Bouchet’s theorem with some minor case analysis.
Bouchet’s original proof is both long and difficult, and relies on nontrivial results from isotropic systems. In this talk I will sketch a simpler, self-contained proof of Bouchet’s theorem with techniques borrowed from Gerards’ proof of Tutte’s excluded-minor characterization of the class of graphic matroids.
This is joint work with Jim Geelen.