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.

Improve this question
$\endgroup$
2
  • 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

Reset to default
5
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 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$
    – user1387682
    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$
    – David Eppstein
    Jun 13, 2016 at 20:05

Your Answer

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

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