# About properties of adjacency matrix when a graph is planar

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?

• Please at least run a spell check before writing your questions. It's not palanr, it's planar Dec 5 '10 at 6:21
• :)) OK Sureh, I promise to do! :) Dec 5 '10 at 7:07
• How about bipartite planar graph? 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! Dec 5 '10 at 18:28
• Is computing a bipartite planar graph permanent easy? Dec 11 '10 at 7:10

## 5 Answers

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.

• Is computing a bipartite planar graph permanent easy? Dec 8 '10 at 0:29
• @Arul Yes, by the FKT algorithm en.wikipedia.org/wiki/FKT_algorithm Apr 14 '12 at 13:17

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:

http://www.jstor.org/pss/2100346