Planarer Graph ist ein Graph, der sich in der Ebene so zeichnen lässt, dass sich keine zwei Kanten überkreuzen. Die Zeichnung teilt die Ebene in Flächen (Gebiete) auf; auch der äußere, unbegrenzte Bereich zählt als Fläche. Planarität ist eine topologische Eigenschaft: Entscheidend ist nicht die konkrete Zeichnung, sondern dass überhaupt eine kreuzungsfreie Anordnung existiert.
Eulersche Polyederformel
Für einen zusammenhängenden planaren Graphen gilt die Eulersche Formel:
Ecken - Kanten + Flächen = 2Ein Würfelgraphen mit 8 Ecken, 12 Kanten und 6 Flächen erfüllt sie beispielsweise: 8 - 12 + 6 = 2. Die Formel ist ein wichtiges Hilfsmittel, um zu beweisen, dass bestimmte Graphen nicht planar sind.
Nicht-planare „Minimalfälle“
- K5: Der vollständige Graph mit fünf Knoten (jeder mit jedem verbunden) ist nicht planar.
- K3,3: Der vollständig bipartite Graph mit drei Knoten pro Teilmenge – das klassische „Häuser-versorgung“-Problem (drei Häuser an drei Versorgungsleitungen) – ist nicht planar.
Nach dem Satz von Kuratowski gilt: Ein Graph ist genau dann planar, wenn er keinen dieser beiden „verbotenen“ Teilgraphen enthält (in einer präzisierten Unterteilungsform).
Färbung und Algorithmen
Jeder planare Graph lässt sich mit höchstens vier Farben so einfärben, dass benachbarte Knoten verschieden sind (Vier-Farben-Satz) – das berühmte Problem der Landkartenfärbung. Die Planaritätsprüfung ist in linearer Zeit möglich (Hopcroft-Tarjan), und viele schwere Graphenprobleme sind auf planaren Graphen leichter lösbar als im Allgemeinfall.
Anwendungen
- Leiterplatten- und Chip-Layout: Verbindungen sollen sich auf einer Ebene nicht kreuzen
- Landkarten: Länder so färben, dass benachbarte Länder nie dieselbe Farbe tragen
- Netzwerkdiagramme: Übersichtliche Topologie-Zeichnungen ohne Kreuzungen, etwa für lokale Netze
In der Praxis sind planare Graphen meist ungerichtete Graphen; ihre Zusammenhangskomponenten und Zyklen verhalten sich wie überall sonst.