A Characterization of Circle Graphs in Terms of Multimatroid Representations

Abstract

The isotropic matroid M[IAS(G)] of a looped simple graph G is a binary matroid equivalent to the isotropic system of G. In general, M[IAS(G)] is not regular, so it cannot be represented over fields of characteristic not equal 2. The ground set of M[IAS(G)] is denoted W(G); it is partitioned into 3-element subsets corresponding to the vertices of G. When the rank function of M[IAS(G)] is restricted to subtransversals of this partition, the resulting structure is a multimatroid denoted Z(3)(G). In this paper we prove that G is a circle graph if and only if for every field F, there is an F-representable matroid with ground set W(G), which defines Z(3)(G) by restriction. We connect this characterization with several other circle graph characterizations that have appeared in the literature.