We introduce a novel linear-algebraic planarity criterion based on the number of spanning trees. We call a matrix an incidence submatrix if each row has at most one 1, at most one -1, and all other entries zero. Given a connected graph G with m edges, we consider the maximum determinant \mathsf{maxdet}(G) of an m \times m matrix [M|N], where M is the incidence matrix of G with one column removed, over all incidence submatrices N of appropriate size, and define its excess to be the number of spanning trees in G minus \mathsf{maxdet}(G). Given a disconnected graph, we define its excess to be the sum of the excesses of its connected components. We show that the excess of a graph is 0 if it is planar, and at least 18 otherwise. This provides a “certificate of planarity” of a planar graph that can be verified by computing the determinant of a sparse matrix and counting spanning trees. Furthermore, we derive an upper bound on the maximum determinant of an m \times m matrix [M|N], where M and N are incidence submatrices. Motivated by this bound and numerical evidence, we conjecture that this maximum determinant is equal to the maximum number of spanning trees in a planar graph with m edges. We present partial progress towards this conjecture. In particular, we prove that the \mathsf{maxdet}(⋅) value of any subdivision of K_{3, 3} or K_5 is at most that of the best planar graph with the same number of edges.