<p>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.</p>

CC BY-SA 2.5
2010-12-05T17:29:47.557Z
2010-12-05T17:29:47.557Z
David Eppstein
<p>Computing determinant and permanent of planar graphs are as hard as computing them in general graphs. They are complete for <strong>GapL</strong> and <strong>#P</strong> respectively. See this paper by <a href="http://portal.acm.org/citation.cfm?id=1714450.1714453">Datta, Kulkarni, Limaye, Mahajan</a> for more details.</p>

CC BY-SA 3.0
2012-04-14T13:17:00.530Z
@Arul Yes, by the FKT algorithm http://en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
CC BY-SA 2.5
2010-12-08T00:29:53.553Z
Is computing a bipartite planar graph permanent easy?
Turbo
CC BY-SA 2.5
2010-12-05T06:21:30.950Z
2010-12-05T06:21:30.950Z
Shiva Kintali
<p>There is a property of the <strong>distance matrix</strong> (and not the adjacency matrix) of <em>restricted</em> planar graphs that might be of interest, the <strong>Monge property</strong>. 
The Monge property (due to Gaspard Monge) for planar graphs essentially means that <em>certain</em> shortest paths cannot cross. See <a href="http://en.wikipedia.org/wiki/Monge_array">Wikipedia: Monge Array</a> for a formal description of the Monge property. <a href="http://dx.doi.org/10.1007/3-540-62559-3_14">Djidjev (WG 1996)</a> (<a href="http://public.lanl.gov/djidjev/papers/planar-spp.ps">paper on Djidjev's website</a>) and <a href="http://dx.doi.org/10.1016/j.jcss.2005.05.007">Fakcharoenphol and Rao (FOCS 2001)</a> (<a href="http://courses.csail.mit.edu/6.889/fall11/lectures/L12.html">Video</a>) show how to exploit the non-crossing properties in shortest-path algorithms. </p>

CC BY-SA 3.0
2012-04-06T14:14:27.047Z
2012-04-06T14:14:27.047Z
Christian Sommer
<p>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). <a href="http://arxiv.org/abs/0907.1591">See for example this paper</a>. </p>

CC BY-SA 2.5
2010-12-05T06:26:26.657Z
2010-12-05T06:26:26.657Z
Suresh Venkat
<p>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:</p>

<p><a href="http://www.jstor.org/pss/2100346">http://www.jstor.org/pss/2100346</a></p>

CC BY-SA 2.5
2010-12-05T17:45:57.093Z
2010-12-05T17:45:57.093Z
Joseph Malkevitch
<p>1- Is there any specific properties for adjacency matrix when a graph is planar?<br>
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?</p>

CC BY-SA 3.0
2012-04-14T13:20:28.700Z
@Arul You are correct. It is by the FKT algorithm http://en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
CC BY-SA 2.5
2010-12-05T06:21:46.270Z
Please at least run a spell check before writing your questions. It's not palanr, it's planar
Suresh Venkat
CC BY-SA 2.5
2010-12-05T07:07:27.867Z
:)) OK Sureh, I promise to do! :)
marjoonjan
CC BY-SA 2.5
2010-12-05T11:18:14.873Z
How about bipartite planar graph?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-05T18:28:08.273Z
I personaly dont care about bipartite planar graph, but if it is any thing in your mind, it is welcome! share it please!
marjoonjan
CC BY-SA 2.5
2010-12-11T07:10:23.087Z
Is computing a bipartite planar graph permanent easy?
Turbo
CC BY-SA 2.5
2010-12-11T11:44:42.340Z
@Arul: I dont get what you mean by "Computing a bipartite planar graph", you mean counting perfect matching in a planar bipartite graph?
marjoonjan
CC BY-SA 2.5
2010-12-12T02:04:59.213Z
Please read as "computing a 'bipartite planar graph' permanent" in other words is calculating permanent of a bipartite planar graph easy?
Turbo
CC BY-SA 2.5
2010-12-12T08:33:43.887Z
I don’t think so, because computing the permanent for a bipartite graph is equal to counting the number of matching in that bipartite graph. There are some results about counting the number of matching and perfect matching in bipartite graphs, and therefore for computing the permanent. 
I ask you to read "The complexity of counting in sparse, regular, and planar graphs" by Salil p. Vadhan, this paper is free and you can catch it. I don’t know the answer for every arbitrary planar bipartite graph, although it seems to be #p-comp, but following results are known to be #p-comp
(in next comment)
marjoonjan
CC BY-SA 2.5
2010-12-12T08:34:21.997Z
The number of matching in a planar bipartite graph of degree at most 6; The number of perfect matching in a k-regular bipartite graph;
 The number of matching in a bipartite graph of degree at most 4- ...
marjoonjan
CC BY-SA 2.5
2010-12-13T01:59:14.780Z
I thought the permanent of a bipartite planar graph can be quickly computed in terms of the underlying determinant of the Pfaffian. I assumed this would be the case.
Turbo
<graph-theory><co.combinatorics><permanent>
About properties of adjacency matrix when a graph is planar
marjoonjan
# About properties of adjacency matrix when a graph is planar

(Asked by: username_0 on 2010-12-05)

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?

**Tags:** graph-theory, co.combinatorics, permanent
> **Comments:**
> **username_2**: Please at least run a spell check before writing your questions. It's not palanr, it's planar  
> **username_0**: :)) OK Sureh, I promise to do! :)  
> **username_3**: How about bipartite planar graph?  
> **username_0**: I personaly dont care about bipartite planar graph, but if it is any thing in your mind, it is welcome! share it please!  
> **username_4**: Is computing a bipartite planar graph permanent easy?  
> **username_0**: @Arul: I dont get what you mean by "Computing a bipartite planar graph", you mean counting perfect matching in a planar bipartite graph?  
> **username_4**: Please read as "computing a 'bipartite planar graph' permanent" in other words is calculating permanent of a bipartite planar graph easy?  
> **username_0**: I don’t think so, because computing the permanent for a bipartite graph is equal to counting the number of matching in that bipartite graph. There are some results about counting the number of matching and perfect matching in bipartite graphs, and therefore for computing the permanent.  I ask you to read "The complexity of counting in sparse, regular, and planar graphs" by Salil p. Vadhan, this paper is free and you can catch it. I don’t know the answer for every arbitrary planar bipartite graph, although it seems to be #p-comp, but following results are known to be #p-comp (in next comment)  
> **username_0**: The number of matching in a planar bipartite graph of degree at most 6; The number of perfect matching in a k-regular bipartite graph;  The number of matching in a bipartite graph of degree at most 4- ...  
> **username_4**: I thought the permanent of a bipartite planar graph can be quickly computed in terms of the underlying determinant of the Pfaffian. I assumed this would be the case.  
> **username_1**: @Arul You are correct. It is by the FKT algorithm http://en.wikipedia.org/wiki/FKT_algorithm  

---

## 5 answers

### Answer by username_6 on 2010-12-05. Score: 26

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](http://portal.acm.org/citation.cfm?id=1714450.1714453) for more details.

> **Comments:**
> **username_4**: Is computing a bipartite planar graph permanent easy?  
> **username_1**: @Arul Yes, by the FKT algorithm http://en.wikipedia.org/wiki/FKT_algorithm  

---

### Answer by username_5 on 2010-12-05. Score: 16

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.


---

### Answer by username_7 on 2012-04-06. Score: 10

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](http://en.wikipedia.org/wiki/Monge_array) for a formal description of the Monge property. [Djidjev (WG 1996)](http://dx.doi.org/10.1007/3-540-62559-3_14) ([paper on Djidjev's website](http://public.lanl.gov/djidjev/papers/planar-spp.ps)) and [Fakcharoenphol and Rao (FOCS 2001)](http://dx.doi.org/10.1016/j.jcss.2005.05.007) ([Video](http://courses.csail.mit.edu/6.889/fall11/lectures/L12.html)) show how to exploit the non-crossing properties in shortest-path algorithms.


---

### Answer by username_2 on 2010-12-05. Score: 6

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](http://arxiv.org/abs/0907.1591).


---

### Answer by username_8 on 2010-12-05. Score: 6

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>


---

