Planar graphs can be characterized in terms of various minor monotone graph invariants such as $\mu(G)$ of Colin de Verdière, $\lambda(G)$ of Van der Holst, Laurent and Schrijver, or the recent $\sigma(G)$ of Van der Holst and Pendavingh. A graph $G$ is planar if and only if $\mu(G)$, $\lambda(G)$ or $\sigma(G)\leq 3$.
You can relax this to $\leq 4$, which turns out to be the flat graphs $G$, those that are linklessly embeddable in 3-space. A linkless embedding can be found in polynomial time (Van der Holst) (checking planarity is linear - Hopcroft and Tarjan). There are many connections to linear algbraalgebra, topology, and combinatorial geometry.
Also, since $\mu(G)\leq 2$ if and only if $\sigma(G)\leq 2$ if and only if $G$ is outerplanar, outerplanarity can be considered to be a natural strengthening of planarity (which goes in the opposite direction from that asked by the question).
Note: There is also a $\lambda(G)$ of Van der Holst, Laurent and Schrijver (paper) which does not characterize planarity. Instead, $\lambda(G)\leq 3$ iff $G$ does not have $K_5$ or a certain graph $V_8$ as minor.
