# Mac Lane's planarity criterion and 2-bases

Mac Lane's planarity criterion states that a graph is planar if and only if its cycle space has a basis such that each edge is contained in at most two cycles. We call a basis with this property a 2-basis. Finding a 2-basis for a planar graph is easy; just find an embedding of the graph in the plane and use the faces of the graph as the cycle basis.

I am interested in the more general algebraic version of this problem. Given a finite dimensional vector space $$V$$ over $$\mathbb{Z}_2$$ and a basis $$B$$, can I determine if $$V$$ has a 2-basis? That is, does there exist an algorithm that takes $$B$$ as input and produces a 2-basis if one exists?

I have not encountered any references to the idea of a 2-basis outside of planar graphs. Have these bases been studied in any other context? What is known about them?

## 1 Answer

Let's see if I can get this straight.

So a binary vector space has a 2-basis if and only if it is a cographic matroid (i.e., the dual of a graphic matroid).

An equivalent matroid-terminology-free statement is that a binary vector space has a 2-basis if and only if it is the cocycle space of a graph (i.e. the vector space generated by all edge-cuts of the graph).

MacLane's result arises because if a binary vector space is simultaneously the cycle space of a graph and the cocycle space of a graph then it is planar.

As far as I know, this is due to Dominic Welsh in the paper "On the hyperplanes of a matroid" (https://doi.org/10.1017/S0305004100044017) where he called it a "2-complete basis".