<p>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 <a href="https://en.wikipedia.org/wiki/Whitney%27s_planarity_criterion" rel="noreferrer">Whitney's planarity criterion</a>. But it uses the incidence matrix, not the adjacency matrix, and is a mathematical criterion rather than a polynomial time algorithm.</p>

<p>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.</p>

CC BY-SA 3.0
2016-06-13T16:15:24.973Z
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
CC BY-SA 3.0
2016-06-13T16:25:09.580Z
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
CC BY-SA 3.0
2016-06-13T20:05:05.730Z
You didn't ask for a non-complex-to-implement criterion, you asked for a matrix-based one.
David Eppstein
CC BY-SA 3.0
2016-06-11T22:44:13.387Z
2016-06-11T22:44:13.387Z
David Eppstein
<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2016-06-11T22:50:37.513Z
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
CC BY-SA 3.0
2016-06-12T05:13:41.763Z
It would beneficial if you add a motivation section to your post and explain why you are interested in this.
Kaveh
<ds.algorithms><graph-theory><graph-algorithms><planar-graphs><polynomial-time>
Graph planarity testing via adjacency matrix
user1387682
# Graph planarity testing via adjacency matrix

(Asked by: username_0 on 2016-06-11)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, planar-graphs, polynomial-time

> **Comments:**
> **username_1**: 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.  
> **username_2**: It would beneficial if you add a motivation section to your post and explain why you are interested in this.  

---

## 1 answers

### Answer by username_3 on 2016-06-11. Score: 5

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](https://en.wikipedia.org/wiki/Whitney%27s_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.

> **Comments:**
> **username_0**: 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  
> **username_0**: 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?  
> **username_3**: You didn't ask for a non-complex-to-implement criterion, you asked for a matrix-based one.  

---

