Implementing Bixby and Wagner's Almost-Linear-Time Algorithm for Graph Realization

The study of matroid theory unites topics from graph theory, linear algebra, combinatorial optimization, and many other fields. An important problem in matroid theory, called the graph realization problem, is recognizing when a given binary matroid is graphic. We present a thorough treatment of an almost-linear-time algorithm due to Bixby and Wagner that solves this problem. Along the way, we consider the important graph-theoretic concept of 2-isomorphism and the related hypopath problem. Finally, we present specific details on implementation of the algorithm, as well as explore several practical applications of the algorithm.