Informationen zu Eigenschaften der Adjazenzmatrix, wenn ein Diagramm planar ist

21

1- Gibt es spezielle Eigenschaften für die Adjazenzmatrix, wenn ein Diagramm planar ist?
2- Gibt es etwas Besonderes für die Berechnung der permanenten Adjazenzmatrix, wenn ein Graph planar ist?

graph-theory co.combinatorics permanent Marjoonjan
quelle
8
Bitte führen Sie mindestens eine Rechtschreibprüfung durch, bevor Sie Ihre Fragen schreiben. Es ist nicht palanr, es ist planar
Suresh Venkat
:)) OK Sureh, ich verspreche es zu tun! :)
marjoonjan
Wie wäre es mit einem zweigliedrigen planaren Graphen?
Mohammad Al-Turkistany
Ich persönlich interessiere mich nicht für zweigliedrige ebene Graphen, aber wenn es etwas in Ihrem Kopf ist, ist es willkommen! teile es bitte!
marjoonjan
Ist die Berechnung eines zweigliedrigen planaren Graphen dauerhaft einfach?
T ....

Antworten:

15

Es ist eher eine Eigenschaft der Inzidenzmatrix als der Adjazenzmatrix, aber eine wichtige Eigenschaft planarer Graphen ist, dass es sich genau um die Graphen handelt, deren Grafik-Matroid das Dual einer anderen Grafik-Matroid ist. Die Beziehung zu Inzidenzmatrizen besteht darin, dass die grafische Matrix Sätze unabhängiger Spalten in der Matrix beschreibt.

David Eppstein
quelle
9

Es gibt eine Eigenschaft der Distanzmatrix (und nicht der Adjazenzmatrix) von eingeschränkten planaren Graphen, die von Interesse sein könnte, die Monge-Eigenschaft . Die Monge-Eigenschaft (aufgrund von Gaspard Monge) für planare Diagramme bedeutet im Wesentlichen, dass sich bestimmte kürzeste Pfade nicht kreuzen können. Eine formale Beschreibung der Eigenschaft Monge finden Sie in Wikipedia: Monge Array . Djidjev (WG 1996) ( Artikel auf Djidjevs Website ) und Fakcharoenphol und Rao (FOCS 2001) ( Video ) zeigen, wie man die Nichtkreuzungseigenschaften in Algorithmen für kürzeste Wege ausnutzt.

Christian Sommer
quelle
6

Ich bin nicht sicher, welche Art von Eigenschaften Sie suchen, aber der Spektralradius von planaren Graphen ist eine solche Größe (der maximale Absolutwert eines Eigenwerts der Adjazenymatrix). Siehe zum Beispiel dieses Papier .

Suresh Venkat
quelle
6

Obwohl dies nicht direkt mit Ihrer Frage zusammenhängt, möchten Sie vielleicht einen Blick auf die Arbeit mit Gradfolgen planarer Graphen werfen. Es sind keine Charakterisierungen bekannt, wann eine Gradfolge die Gradfolge eines planaren Graphen ist. Es gibt jedoch eine Reihe interessanter Artikel zu solchen Themen, darunter:

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

Joseph Malkevitch
quelle