1- Is there any specific properties for adjacency matrix when a graph is planar?
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?

  • 8
    Please at least run a spell check before writing your questions. It's not palanr, it's planar – Suresh Venkat Dec 5 '10 at 6:21
  • :)) OK Sureh, I promise to do! :) – marjoonjan Dec 5 '10 at 7:07
  • How about bipartite planar graph? – Mohammad Al-Turkistany Dec 5 '10 at 11:18
  • I personaly dont care about bipartite planar graph, but if it is any thing in your mind, it is welcome! share it please! – marjoonjan Dec 5 '10 at 18:28
  • Is computing a bipartite planar graph permanent easy? – Brout Dec 11 '10 at 7:10

Computing determinant and permanent of planar graphs are as hard as computing them in general graphs. They are complete for GapL and #P respectively. See this paper by Datta, Kulkarni, Limaye, Mahajan for more details.

It's more a property of the incidence matrix than the adjacency matrix, but one important property of planar graphs is that they are exactly the graphs whose graphic matroid is the dual of another graphic matroid. The relation to incidence matrices is that the graphic matroid describes sets of independent columns in the matrix.

There is a property of the distance matrix (and not the adjacency matrix) of restricted planar graphs that might be of interest, the Monge property. The Monge property (due to Gaspard Monge) for planar graphs essentially means that certain shortest paths cannot cross. See Wikipedia: Monge Array for a formal description of the Monge property. Djidjev (WG 1996) (paper on Djidjev's website) and Fakcharoenphol and Rao (FOCS 2001) (Video) show how to exploit the non-crossing properties in shortest-path algorithms.

I'm not sure what kind of properties you're looking for but the spectral radius of planar graphs is one such quantity (the max absolute value of an eigenvalue of the adjaceny matrix). See for example this paper.

While not directly related to your question you might want to look at the work on degree sequences of planar graphs. There are no known characterizations of when a degree sequence is the degree sequence of a planar graph. However, there are a variety of interesting papers about such matters including:


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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