A new characterization of graphic matroids (Q958686)

A graph is planar if and only if the dual of its cycle matroid is graphic. A result of Tutte establishes a necessary condition for a matroid to be graphic, that any cocircuit has bipartite avoidance graph. \textit{J.C. Fournier} [J. Comb. Theory, Ser. B 16, 181-190 (1974; Zbl 0271.05010] proved that a matroid is graphic if and only if, for any three cocircuits \(X_1\), \(X_2\), \(X_3\) with a common element, one of them separates the other two, e.g., \(X_2 \setminus X_1\) and \(X_3 \setminus X_1\) are contained in different components of \(M \setminus X_1.\) (Necessity for cographic matroids is a consequence of the Jordan Curve Theorem.) In the paper under review, the author combines these two results to obtain necessary and sufficient conditions for a (binary) matroid to be graphic that depend only on properties of fundamental cocircuits relative to a single basis \(B\) of \(M=M(E).\) This yields a more efficient test for planarity of graphs. The precise result is: a binary matroid is graphic if and only if every fundamental cocircuit has bipartite avoidance graph and, for any three fundamental cocircuits with a point in common, one of them separates the other two. The proof is by induction, involving a careful analysis of the fundamental (bipartite) graph of \(M\) relative to \(B,\) having vertex set \(E\) and \(e \in E - B\) adjacent to \(f \in B\) when \(e\) and \(f\) lie in a circuit in \(B \cup e\).