A propos des propriétés de la matrice d'adjacence lorsqu'un graphe est plan

21

1- Existe-t-il des propriétés spécifiques pour la matrice d'adjacence lorsqu'un graphe est plan?
2- Y a-t-il quelque chose de spécial pour calculer la matrice permanente d'adjacence lorsqu'un graphe est plan?

graph-theory co.combinatorics permanent marjoonjan
la source
8
Veuillez au moins effectuer une vérification orthographique avant d'écrire vos questions. Ce n'est pas palanr, c'est planaire
Suresh Venkat
:)) OK Sureh, je promets de le faire! :)
marjoonjan
Que diriez-vous d'un graphique plan bipartite?
Mohammad Al-Turkistany
Personnellement, je ne me soucie pas du graphique plan bipartite, mais si c'est quelque chose dans votre esprit, c'est le bienvenu! partagez-le s'il vous plaît!
marjoonjan
Est-il facile de calculer un graphe planaire bipartite en permanence?
T ....

Réponses:

25

Le calcul déterminant et permanent des graphes planaires est aussi difficile que leur calcul dans les graphes généraux. Ils sont complets pour GapL et #P respectivement. Voir cet article de Datta, Kulkarni, Limaye, Mahajan pour plus de détails.

Shiva Kintali
la source
Est-il facile de calculer un graphe planaire bipartite en permanence?
T ....
@Arul Oui, par l'algorithme FKT en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
15

C'est plus une propriété de la matrice d'incidence que la matrice d'adjacence, mais une propriété importante des graphes planaires est qu'ils sont exactement les graphes dont le matroïde graphique est le double d'un autre matroïde graphique. La relation avec les matrices d'incidence est que le matroïde graphique décrit des ensembles de colonnes indépendantes dans la matrice.

David Eppstein
la source
9

Il existe une propriété de la matrice de distance (et non la matrice d'adjacence) des graphes planaires restreints qui pourrait être intéressante, la propriété Monge . La propriété Monge (due à Gaspard Monge) pour les graphes planaires signifie essentiellement que certains chemins les plus courts ne peuvent pas se croiser. Voir Wikipedia: Monge Array pour une description formelle de la propriété Monge. Djidjev (WG 1996) ( article sur le site Web de Djidjev ) et Fakcharoenphol et Rao (FOCS 2001) ( Vidéo ) montrent comment exploiter les propriétés de non-croisement dans les algorithmes à plus court chemin.

Christian Sommer
la source
6

Je ne sais pas quel type de propriétés vous recherchez, mais le rayon spectral des graphes planaires est l'une de ces quantités (la valeur absolue maximale d'une valeur propre de la matrice adjacente). Voir par exemple ce document .

Suresh Venkat
la source
6

Bien que n'étant pas directement lié à votre question, vous voudrez peut-être regarder le travail sur les séquences de degrés des graphiques planaires. Il n'y a aucune caractérisation connue du moment où une séquence de degrés est la séquence de degrés d'un graphe planaire. Cependant, il existe une variété d'articles intéressants sur ces questions, notamment:

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

Joseph Malkevitch
la source