Ebener Graph

Ein ebener Graph ist eine konkrete Darstellung eines Graphen als Teilmenge des ${\mathbb {R}}^{2}$ und damit ein Spezialfall eines euklidischen Graphen für q=2 .

Definition

Ein Tupel (V,E) (wobei die Elemente aus Ecken genannt werden und die Elemente aus Kanten) heißt ein ebener Graph, wenn gilt:

besteht aus paarweise disjunkten Punkten des ${\mathbb {R}}^{2}$ .
Jede Kante ist eine einfache Jordankurve, die zwei Ecken miteinander verbindet.
Die Kanten schneiden sich nie und berühren sich bloß in den Ecken.

Teilweise wird in der Literatur auch noch folgende vierte Bedingung gestellt:

Verschiedene Ecken werden durch verschiedene Kanten verbunden.

Diese Verschärfung wird oftmals gefordert, wenn man nur einfache Graphen auf Planarität untersuchen will. Die obigen drei Punkte lassen noch Multigraphen als betrachteten Gegenstand zu.

Ein ebener Graph heißt maximal eben, wenn er eben ist, aber nach dem hinzufügen einer beliebigen Kante nicht mehr eben ist.

Abgrenzung zu planaren Graphen

Beispielgraphen G1 und G2

Bei ebenen Graphen besteht oftmals eine Verwechslungsgefahr zu den planaren Graphen: Planarität ist eine Eigenschaft von abstrakten Graphen, also Graphen, aufgefasst als eine Knotenmenge und je nach Definition unterschiedliche Kantenmenge. Ein ebener Graph jedoch ist eine Darstellung eines abstrakten Graphen als Teilmenge des ${\mathbb {R}}^{2}$ . So ist im obigen Bild $G_{1}$ eben. Betrachtet man $G_{2}$ als Teilmenge des ${\mathbb {R}}^{2}$ , so muss dieser erst anders gezeichnet werden, um einen ebenen Graphen zu erhalten. Der zugrunde liegende abstrakte Graph $G_{2}$ ist aber planar unabhängig davon, wie man ihn im konkreten Fall zeichnet. Definitionsgemäß sind die planaren Graphen genau diejenigen Graphen, die zu einem ebenen Graphen isomorph sind.

Eigenschaften

Für zusammenhängende ebene Graphen gilt nach dem eulerschen Polyedersatz:

n-m+f=2 , wobei n=|V| , m=|E| und die Anzahl der Flächen des Graphen ist (die äußere Fläche mitgerechnet)

Jeder maximal ebene Graph ist maximal planar

Basierend auf einem Artikel in:

Wikipedia.de