A constructive characterisation of circuits in the simple $(2,1)$-sparse matroid

Abstract

A simple graph $G=(V,E)$ is a $(2,1)$-circuit if $|E|=2|V|$ and $|E(H)|\le 2|V(H)|-1$ for every proper subgraph $H$ of $G$. Motivated, in part, by ongoing work to understand unique realisations of graphs on surfaces, we derive a constructive characterisation of $(2,1)$-circuits. The characterisation uses the well known 1-extension and $X$-replacement operations as well as several summation moves to glue together $(2,1)$-circuits over small cutsets.

arXiv comment25 pages, 17 figures, revised following reviewer comments