Planare Graphen

Neue Frage »

binary Auf diesen Beitrag antworten »
Planare Graphen
Hallo!

Wie prüft man Graphen eigentlich am besten auf Planarität?
Gibt es da ein recht schnelles, sicheres Kriterium, das man von Hand ausführen kann, wenn man den Graph zB als Adjazenzmatrix gegeben hat?

Oder muss ich mir den Graph dann hinmalen und gut draufgucken?
papahuhn Auf diesen Beitrag antworten »

Notwendige Bedingung für planare, schlichte Graphen: Anzahl Kanten <= 3 * Anzahl Ecken - 6.
Ansonsten mal nach dem Satz von Kuratowski googlen.
eon_hummel Auf diesen Beitrag antworten »
Adjazenzmatrix - planar oder nicht?
Hallo,

ich weiß, der Thread ist schon etwas älter, er passt aber sehr gut zu meiner Frage.

Ich habe einen (ungerichteten) Graphen als (symmetrische) Adjazenzmatrix (ohne Schleifen) gegeben und will ihn nun auf Planarität prüfen. Dabei reicht mir die notwendige Bedingung nicht aus, ich hätte gerne eine hinreichende. Mein Problem ist, dass es sich bei meiner Programmierung um viele tausend Adjazenzmatrizen handelt, die zu zeichnen viel zu lange dauern würde. Außerdem reichen dafür womöglich meine Programmierfähigkeiten nicht aus.

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

Ich danke von Herzen!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »