Rotation system

In combinatorial mathematics, rotation systems encode embeddings of graphs onto orientable surfaces, by describing the circular ordering of a graph's edges around each vertex.A more formal definition of a rotation system involves pairs of permutations; such a pair is sufficient to determine a multigraph, a surface, and a 2-cell embedding of the multigraph onto the surface.

Every rotation scheme defines a unique 2-cell embedding of a connected multigraph on a closed oriented surface (up to orientation preserving topological equivalence). Conversely, any embedding of a connected multigraph "G" on an oriented closed surface defines a unique rotation system having "G" as its underlying multigraph. This fundamental equivalence between rotation systems and 2-cell-embeddings was first settled in a dual form by Heffter and extensively used by Ringel during the 1950s. Independently, Edmonds gave the primal form of the theorem and the details of his study have been popularized by Youngs. The generalization to the whole set of multigraphs was developed by Gross and Alpert.

Rotation systems are related to, but not the same as, the "rotation maps" used by Reingold et al. (2002) to define the zig-zag product of graphs. A rotation system specifies a circular ordering of the edges around each vertex, while a rotation map specifies a (non-circular) permutation of the edges at each vertex. In addition, rotation systems can be defined for any graph, while as Reingold et al define them rotation maps are restricted to regular graphs.

Formal definition

Formally, a rotation system is defined as a pair (σ,θ) where σ and θ are permutations acting on the same ground set "B", θ is a fixed-point-free involution, and the group <σ,θ> generated by σ and θ acts transitively on "B".

To derive a rotation system from a 2-cell embedding of a connected multigraph "G" on an oriented surface, let "B" consist of the "darts" (or "flags", or "half-edges") of "G"; that is, for each edge of "G" we form two elements of "B", one for each endpoint of the edge. Even when an edge has the same vertex as both of its endpoints, we create two darts for that edge. We let θ("b") be the other dart formed from the same edge as "b"; this is clearly an involution with no fixed points. We let σ("b") be the dart in the clockwise position from "b" in the cyclic order of edges incident to the same vertex, where "clockwise" is defined by the orientation of the surface.

If a multigraph is embedded on an orientable but not oriented surface, it generally corresponds to two rotation systems, one for each of the two orientations of the surface. These two rotation systems have the same involution θ, but the permutation σ for one rotation system is the inverse of the corresponding permutation for the other rotation system.

Recovering the embedding from the rotation system

To recover a multigraph from a rotation system, we form a vertex for each orbit of σ, and an edge for each orbit of θ. A vertex is incident with an edge if these two orbits have a nonempty intersection. Thus, the number of incidences per vertex is the size of the orbit, and the number of incidences per edge is exactly two. If a rotation system is derived from a 2-cell embedding of a connected multigraph "G", the graph derived from the rotation system is isomorphic to "G".

To embed the graph derived from a rotation system onto a surface, form a disk for each orbit of σθ, and glue two disks together along an edge "e" whenever the two darts corresponding to "e" belong to the two orbits corresponding to these disks. The result is a 2-cell embedding of the derived multigraph, the two-cells of which are the disks corresponding to the orbits of σθ. The surface of this embedding can be oriented in such a way that the clockwise ordering of the edges around each vertex is the same as the clockwise ordering given by σ.

Characterizing the surface of the embedding

According to the Euler formula we can deduce the genus "g" of the closed orientable surface defined by the rotation system $(sigma,\; heta)$ (that is, the surface on which the underlying multigraph is 2-cell embedded): [harvtxt|Lando|Zvonkin|2004, formula 1.3, p. 38.]

:$g=1-frac\{1\}\{2\}(|Z(sigma)|-|Z(\; heta)|+|Z(sigma\; heta)|)$

where $Z(phi)$ denotes the set of the orbits of permutation $phi$.

Notes

References

*cite journal
author = R. Cori and A. Machì
title = Maps, hypermaps and their automorphisms: a survey
journal = Expositiones Mathematicae
volume = 10
year = 1992
pages = 403–467
id = MathSciNet | id = 1190182

*cite journal
author = J. Edmonds
authorlink = Jack Edmonds
title = A combinatorial representation for polyhedral surfaces
journal = Notices of the American Mathematical Society
volume = 7
year = 1960
pages = 646

*cite journal
author = J. L. Gross, and S. R. Alpert
title = The topological theory of current graphs
journal = Journal of Combinatorial Theory, Series B
volume = 17
year = 1974
pages = 218–233
id = MathSciNet | id = 0363971
doi = 10.1016/0095-8956(74)90028-8

*cite journal
author = L. Heffter
title = Über das Problem der Nachbargebiete
journal = Mathematische Annalen
volume = 38
issue = 4
year = 1891
pages = 477–508
doi = 10.1007/BF01203357

*.

*cite book
author = Bojan Mohar and Carsten Thomassen
title = Graphs on Surfaces
publisher = The Johns Hopkins University Press
year = 2001
id = ISBN 0801866898

*cite journal
author = O. Reingold, S. Vadhan, and A. Wigderson
title = Entropy waves, the zig-zag graph product, and new constant-degree expanders
journal = Annals of Mathematics
volume = 155
issue = 1
year = 2002
pages = 157–187
url = http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.annm/1032209948
id = MathSciNet | id = 1888797
doi = 10.2307/3062153

*cite journal
author = G. Ringel
authorlink = Gerhard Ringel
title = Das Geschlecht des vollständigen paaren Graphen
journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
volume = 28
year = 1965
pages = 139–150
id = MathSciNet | id = 0189012

*cite journal
author = J. W. T. Youngs
title = Minimal imbeddings and the genus of a graph
journal = Journal of Mathematics and Mechanics
volume = 12
year = 1963
pages = 303–315
id = MathSciNet | id = 0145512
doi = 10.1512/iumj.1963.12.12021