  We consider quantum error-correcting subsystem codes whose gauge generators
realize a translation-invariant, free-fermion-solvable spin model. In this
setting, errors are suppressed by a Hamiltonian whose terms are the gauge
generators of the code and whose exact spectrum and eigenstates can be found
via a generalized Jordan-Wigner transformation. Such solutions are
characterized by the frustration graph of the Hamiltonian: the graph whose
vertices are Hamiltonian terms, which are neighboring if the terms anticommute.
We provide methods for embedding a given frustration graph in the
anticommutation relations of a spin model and present the first known example
of an exactly solvable spin model with a two-dimensional free-fermion
description and exact topological qubits. This model can be viewed as a
free-fermionized version of the two-dimensional Bacon-Shor code. Using
graph-theoretic tools to study the unit cell, we give an efficient algorithm
for deciding if a given translation-invariant spin model is solvable, and
explicitly construct the solution. Further, we examine the energetics of these
exactly solvable models from the graph-theoretic perspective and show that the
relevant gaps of the spin model correspond to known graph-theoretic quantities:
the skew energy and the median eigenvalue of an oriented graph. Finally, we
numerically search for models which have large spectral gaps above the ground
state spin configuration and thus exhibit particularly robust thermal
suppression of errors. These results suggest that optimal models will have low
dimensionality and odd coordination numbers, and that the primary limit to
energetic error suppression is the skew energy difference between different
symmetry sectors rather than single-particle excitations of the free fermions.
