Planarer Graph

Eine konkrete Darstellung eines Graphen in Ebene wird auch Einbettung genannt. Durch die Einbettung wird die in zusammenhängende Gebiete geteilt die von den Kanten des begrenzt werden. Die begrenzenden Kanten eines Gebietes seinen Rand . Das Gebiet um den Graphen herum auch äußeres Gebiet genannt. Die Einbettung kann auch auf Kugeloberfläche stattfinden. Umgekehrt ist auch jeder auf Kugel kreuzugsfrei Darstellbare Graph planar.

Zwei Einbettungen sind äquivalent wenn es Abbildung zwischen den Rändern der ihrer Gebiete Es lässt sich zeigen dass für jeden Graph auch eine Einbettung existiert bei der Kanten Geraden sind.

Ein Graph heißt maximal planar oder Dreiecksgraph wenn er planar ist und ihm Kante hinzugefügt werden kann ohne dass dadurch Planarität verloren geht.

Die Planarität eines Graphen lässt sich verschiedenen Algorithmen in linearer Zeit testen. Allerdings diese Algorithmen nicht sehr einfach zu implementieren.

Verbindung zu anderen Graph-Eigenschaften

In einem zusammenhängenden planaren Graphen gilt nach dem eulerschen Polyedersatz stets:

Knotenanzahl + Gebietsanzahl = Kantenanzahl + 2

Aus dieser Eigenschaft folgt dass planare in Bezug auf die Knotenanzahl nur linear Kanten haben können.

Ist ein planarer Graph 3-fach zusammenhängend so sind alle seine Einbettungen äquivalent.

Der Vier-Farben-Satz besagt dass sich planare Graphen mit Farben färben lassen. Dreiecksfreie planare Graphen sind 3-färbbar.

Ein planarer Graph kann höchstens 5-fach zusammenhängend sein.

siehe auch Topologische Graphentheorie

Bücher zum Thema Planarer Graph

Dieser Artikel von Wikipedia unterliegt der GNU FDL.