Graph planarity testing via adjacency matrix I have looked at several efficient graph planarity algorithms which 
rely on computing and traversing DFS trees
(that add one vertex/edge/path at a time).

I am looking for graph planarity algorithms based on 
the adjacency matrix and operations on it, e.g. 
taking the square of the matrix, 
computing the eigenvalues of the matrix, etc.
Ignoring trivial responses like, recreate the graph from the matrix and apply any standard planarity algorithm, the closest I know of to a matrix-based planarity test is Whitney's planarity criterion. But it uses the incidence matrix, not the adjacency matrix, and is a mathematical criterion rather than a polynomial time algorithm.

It states that a graph is planar if and only if its matroid (the independence matroid of the columns of the signed incidence matrix) has a dual (the matroid for the dual space of the column space) which is also a graphic matroid.