Planarität

Planarität bezeichnet in der Mathematik die Eigenschaft, in einer Ebene darstellbar zu sein. Geometrisch bedeutet dies, dass eine Kurve oder Fläche in einem dreidimensionalen Raum (R^3) in einer einzigen Ebene liegt; eine Fläche ist planar, wenn sie selbst eine Ebene ist.

In der Graphentheorie ist ein endlicher Graph planar, wenn er so gezeichnet werden kann, dass keine Kanten sich kreuzen. Die zentrale Charakterisierung lautet: Ein Graph ist planar, wenn er keine Subdivisionen von K5 oder K3,3 als Untergraph enthält (Kuratowskis Satz). Für zusammenhängende planare Graphen gilt die Eulersche Formel v − e + f = 2, wobei v die Zahl der Knoten, e die Zahl der Kanten und f die Zahl der Flächen bezeichnet. Daraus folgen Abschätzungen wie e ≤ 3v − 6 für v ≥ 3; für Graphen mit bestimmten Eigenschaften lassen sich auch strengere Schranken angeben. Außenplanarität ist eine stärkere Bedingung, bei der alle Kanten in der äußeren Fläche liegen.

Planarität findet Anwendung in Kartografie, Schaltungsdesign, Netzwerkplanung und in der graphentheoretischen Modellierung von Strukturen. Planare Graphen lassen sich oft via Dualgraphen behandeln, und es existieren Algorithmen zur Planaritätstests, darunter lineare Zeitkomplexität-Algorithmen von Hopcroft und Tarjan.