Planität

Planität bezeichnet in der Geometrie und Graphentheorie die Eigenschaft, eine Struktur so in der Ebene darstellen zu können, dass sich keine Kanten schneiden. Eine solche Darstellung wird als planare Einbettung oder Planarzeichnung bezeichnet; ein Graph, der eine solche Einbettung besitzt, ist planar.

Zentrale Theoreme: Ein endlicher Graph ist planar genau dann, wenn er keinen Subgraph besitzt, der eine Homöomorphie zu K5 oder K3,3 enthält (Kuratowskis Satz). Für zusammenhängende planare Graphen gilt die Euler-Formel V - E + F = 2, wobei F die Anzahl der Flächen der Einbettung in die Ebene ist. Allgemein gilt V - E + F = 1 + c, mit c der Zahl der Komponenten des Graphen.

Planaritätstests gibt es in linearer Zeit. Dazu gehören der Hopcroft-Tarjan-Algorithmus (1974) sowie moderne Implementierungen wie der Boyer–Myrvold-Algorithmus. Begriffe wie Außenplanarität beziehen sich auf Graphen, die sich so in die Ebene einbetten lassen, dass alle Kanten die äußere Fläche berühren; solche Graphen werden als außenplanar bezeichnet.

Anwendungen finden sich unter anderem im Schaltungs- und Netzwerkdesign, in der grafischen Darstellung komplexer Strukturen sowie in der Kartografie. Planität dient zudem als grundlegendes Konzept in der Topologie von Flächen und in der Frage, wie Graphen auf Flächen höherer Genus eingebettet werden können.

---