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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Jun 11, 2016 at 22:50
  • $\begingroup$ It would beneficial if you add a motivation section to your post and explain why you are interested in this. $\endgroup$
    – Kaveh
    Jun 12, 2016 at 5:13

1 Answer 1


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.

  • $\begingroup$ 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 $\endgroup$ Jun 13, 2016 at 16:15
  • $\begingroup$ 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? $\endgroup$ Jun 13, 2016 at 16:25
  • 3
    $\begingroup$ You didn't ask for a non-complex-to-implement criterion, you asked for a matrix-based one. $\endgroup$ Jun 13, 2016 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.