21
$\begingroup$

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?

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

5 Answers 5

26
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is computing a bipartite planar graph permanent easy? $\endgroup$
    – Turbo
    Commented Dec 8, 2010 at 0:29
  • 1
    $\begingroup$ @Arul Yes, by the FKT algorithm en.wikipedia.org/wiki/FKT_algorithm $\endgroup$ Commented Apr 14, 2012 at 13:17
16
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

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

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