Planarität anhand der Adjazenzmatrix?

Question

Ich habe einen (ungerichteten) Graphen als  Adjazenzmatrix gegeben und will ihn nun auf Planarität prüfen. Dabei reicht mir die notwendige Bedingung nicht aus, ich hätte gerne eine hinreichende. 

Gibt es nicht eine Methode, wie man alleine anhand der Adjazenzmatrix feststellen kann, ob der Graph planar ist oder eben nicht?

Answer 1

> Gibt es nicht eine Methode, wie man alleine anhand der Adjazenzmatrix feststellen kann, ob der Graph planar ist oder eben nicht?

Gibt es, den Satz von Kuratowski: ein Graph ist genau dann planar ist, wenn er keinen Teilgraphen besitzt, der ein Unterteilungsgraph des K₅ oder des K_3,3 ist.

Comments

Ja, davon habe ich gehört.
Gucke ich also dann ob in meiner gegebenen Matrix entweder K5 oder K3,3 vorkommt ?

---

Was meinst du mit "vorkommt"? Du darfst Knoten und Kanten entfernen und Knoten zusammenziehen. Wenn du so K₅ oder des K_3,3 bekomment kannst, dann ist der Graph nicht planar. Andernfalls ist er planar.

---

genau das meinte ich
danke