21

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?

marjoonjan
  • 747
  • 4
  • 12
  • 8
    Please at least run a spell check before writing your questions. It's not palanr, it's planar – Suresh Venkat Dec 05 '10 at 06:21
  • :)) OK Sureh, I promise to do! :) – marjoonjan Dec 05 '10 at 07:07
  • How about bipartite planar graph? – Mohammad Al-Turkistany Dec 05 '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 05 '10 at 18:28
  • Is computing a bipartite planar graph permanent easy? – Turbo Dec 11 '10 at 07:10
  • @Arul: I dont get what you mean by "Computing a bipartite planar graph", you mean counting perfect matching in a planar bipartite graph? – marjoonjan Dec 11 '10 at 11:44
  • Please read as "computing a 'bipartite planar graph' permanent" in other words is calculating permanent of a bipartite planar graph easy? – Turbo Dec 12 '10 at 02:04
  • 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 Dec 12 '10 at 08:33
  • 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 Dec 12 '10 at 08:34
  • 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 Dec 13 '10 at 01:59
  • @Arul You are correct. It is by the FKT algorithm http://en.wikipedia.org/wiki/FKT_algorithm – Tyson Williams Apr 14 '12 at 13:20

5 Answers5

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 for more details.

Shiva Kintali
  • 10,578
  • 41
  • 74
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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
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 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.

Christian Sommer
  • 761
  • 6
  • 7
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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
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

Joseph Malkevitch
  • 1,319
  • 6
  • 7