roteringsscheman

Roteringsscheman, im Englischen oft als rotation schemes bezeichnet, sind combinatorische Beschreibungen dafür, wie ein Graph auf einer Oberfläche eingezeichnet wird. Sie fassen die topologischen Informationen einer Einbettung in eine Fläche zusammen, indem sie für jeden Scheitel eine zyklische Ordnung der an ihm angrenzenden Kanten festlegen. Mit Rotationsschemata lässt sich eine beliebige orientierbare oder nicht orientierbare Fläche nur durch solche Ordnungsdaten rekonstruieren.

Formale Definition: Sei G = (V, E) ein Graph und H die Menge der Halbkanten (Enden der Kanten). Ein Rotationsschema ordnet jedem Vertex v ∈ V eine zyklische Ordnung der Kanten um v zu. Aus einer äquivalenten Sicht kann man zwei Permutationen auf H betrachten: α vertauscht die beiden Enden jeder Kante (Bildet die Kantenpaare), und ρ ordnet jeweils die Enden um einen Vertex in Zyklen. Die Embedding-Flächen ergeben sich als die Orbits der Permutation ρ∘α.

Fläche, Genus und Planarität: Die Anzahl der Flächen F ergibt sich aus den Zyklen von ρ∘α. Die Euler-Charakteristik χ = V − E + F liefert das genusbezogene Maß g für orientierbare Flächen über g = (2 − χ)/2. Ein planar embeddings besitzt χ = 2 (und somit genus 0). Rotationsschemata ermöglichen so die Klassifikation von Einbettungen auch ohne konkrete Zeichnung.

Beispiele und Anwendungen: Durch passende Rotationen an den Scheiteln lässt sich z. B. eine planare Einbettung des vollständigen Graphen K4 beschreiben. Rotationsschemata spielen eine zentrale Rolle in der topologischen Graphentheorie, der Theorie der kartografischen Karten (Maps) und bei der Generierung zufälliger Karten bzw. der Untersuchung von Automorphismen von Graphen.