Ebene Einbettung und Planare Graphen

Die Planarität klassifiziert Graphenstrukturen anhand ihrer Eigenschaft, überschneidungsfrei in einer zweidimensionalen Ebene darstellbar zu sein.

• Ebene Einbettung (Plane Graph): Eine Zeichnung $\pi$ heißt eben, wenn sich keine zwei Kantenkurven im Raum kreuzen. Es dürfen keine Kanten $e\ne f\in E(G)$ existieren, bei denen die Kurven $\pi (e)$ und $\pi (f)$ einen gemeinsamen Punkt aufweisen, der kein gemeinsamer Kantenendpunkt (Knoten) ist.
• Planarer Graph: Ein Graph $G$ heißt planar, wenn er mindestens eine zulässige ebene Einbettung besitzt.
• Eigenschaften: Die Eigenschaft der Planarität ist abgeschlossen unter Untergraphen (jeder Untergraph eines planaren Graphen ist zwingend planar). Nicht alle Graphen sind planar (Standard-Gegenbeispiele: vollständiger Graph $K_5$ und vollständiger bipartiter Graph $K_{3,3}$).

Links

• DS_vollständiger_foliensatz.pdf