Einbettung & Planarität & Crossing Number & Petersen-Graph

Wie man bereits bei den einführenden Applets zum Thema Graphen sehen konnte, ist die “graphische” 2D-Repräsentation eines Graphen $G = (V,E)$ oftmals ein sehr nützliches und intuitives Hilfsmittel. Formal spricht man bei dieser Form der Repräsentation eines Graphen $G$ von seiner Einbettung. Eine Einbettung ist eine Abbildung von $V$ nach $\mathbb{R}^2$. Es wird also jedem Knoten des Graphen ein Punkt in der euklidischen Zeichenfläche zugeordnet. Falls $G$ ein ungerichteter Graph ist, werden die Kanten $E$ mit den zugehörigen geraden Verbindungslinien der jeweiligen Punktepaare identifiziert.

Besitzt ein ungerichteter Graph $G$ eine Einbettung derart, dass sich kein Paar von Verbindungskanten überschneidet, so nennt man $G$ planar einbettbar (oder einfach nur planar). Falls $G$ nicht planar einbettbar ist, so gibt es eine Klasse von Einbettungen, welche die Anzahl der Kantenüberschneidungen minimiert. Diese minimale Anzahl von Kantenüberschneidungen wird als die Crossing Number von $G$ bezeichnet. Garey & Johnson konnten 1983 zeigen, dass die Bestimmung der Crossing Number NP-vollständig ist.

Petersen-Graph & Applet

Im nachfolgenden Applet kann man verschiedene Einbettungen des Petersen-Graphen (vgl. auch Wikipdeia kennen lernen. Zum Beispiel gibts es Einbettungen des Graphen, welche die 3-zählige Symmetrie bzw. die 5-zählige Symmetrie hervorheben. Des Weiteren lässt sich der Petersen-Graph so einbetten, dass alle Kanten die selbe euklidische Länge besitzen .

Die crossing number des Petersen-Graph ist $2$. Eine obere Schranke für die crossing number ist dabei über die Einbettung gegeben.

Zur Bedienung des Applets:

• Analog zum Applet auf Was ist ein Graph?.

GraphPetersen.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)