# 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.

• I don't see why it is important to use whole matrix but the running time is not important. Anyways, if you are looking for an easy to explain algorithm, a planar graph does not have K_{3,3} and K_5 as a minor and one can test this in polynomial time. – Saeed Jun 11 '16 at 22:50
• It would beneficial if you add a motivation section to your post and explain why you are interested in this. – Kaveh Jun 12 '16 at 5:13

## 1 Answer

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.

• Thank you for quick answer, but i need some more explanatation - how can it become an algoritm? - can i find a graphic matroid dual in poyinomial time? furt – user1387682 Jun 13 '16 at 16:15
• further more - I see from wikipedia that a graphic matroid must have more forbidden minor to check ( uiform matroid and Fano plane in addtion to M(K_3,3),M(K_5)) doesn't it make the check for planirity much more complex? – user1387682 Jun 13 '16 at 16:25
• You didn't ask for a non-complex-to-implement criterion, you asked for a matrix-based one. – David Eppstein Jun 13 '16 at 20:05