2
$\begingroup$

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.

$\endgroup$
  • 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 '16 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 '16 at 5:13
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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