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?


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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.