The Algebraic Frustration Dimension of a Graph

Abstract

We introduce a new minor monotone graph parameter, the algebraic frustration dimension $\textnormal{frustdim}(G)$ of a graph $G$, as the greatest minimum rank of an optimal solution in a certain family of embedding problems for signed graphs with underlying graph $G.$ Our main results are forbidden minor characterizations of the classes of graphs with $\textnormal{frustdim}$ at most $k$ for $k\in\{0,1,2\}.$ The proofs establish connections to tree-width and related parameters and to minimum rank problems for graphs.