- Rotation system
In combinatorial

mathematics ,**rotation systems**encode embeddings of graphs onto orientablesurface s, by describing thecircular 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 toregular graph s.**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 andCarsten 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

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Squad rotation system**— A squad rotation system is a technique often used in sport, usually association football, which is designed to rest players and give playing time to everyone, rather than to just play the same players in every game. Most football (soccer) teams… … Wikipedia**Food rotation system**— A food rotation system is a front loading shelving unit that organizes and rotates food cans on a first in first out basis (FIFO). An effective food rotation system is essential for storing food to prepare for catastrophes, preventing foodborne… … Wikipedia**International Earth Rotation System**— Der Internationale Dienst für Erdrotation und Referenzsysteme (Kürzel IERS; englisch International Earth Rotation and Reference Systems Service; ehemals auch nur Internationaler Erdrotationsdienst, engl. International Earth Rotation Service) ist… … Deutsch Wikipedia**Rotation (mathematics)**— Rotation of an object in two dimensions around a point O. In geometry and linear algebra, a rotation is a transformation in a plane or in space that describes the motion of a rigid body around a fixed point. A rotation is different from a… … Wikipedia**Rotation in office**— Rotation in office, or term limits, dates back to the American Revolution, and prior to that to the democracies and republics of antiquity. The council of 500 in ancient Athens rotated its entire membership annually, as did the ephorate in… … Wikipedia**Rotation of axes**— is a form of Euclidean transformation in which the entire xy coordinate system is rotated in the counter clockwise direction with respect to the origin (0, 0) through a scalar quantity denoted by θ.With the exception of the degenerate cases, if a … Wikipedia**Rotation-powered pulsar**— is one of the major classes of pulsars. A Rotation powered pulsar is a rapidly rotating neutron star, whose electromagnetic radiation is observed in regularly spaced intervals, or pulses . It differs from other types of pulsars in that the source … Wikipedia**Rotation (pool)**— Rotation, sometimes called rotation pool or 61, is a pocket billiards (pool) game, requiring a standard pool table, Cuegloss|Cue ball|cue ball and triangular rack of fifteen pool balls, in which the lowest numbered Cuegloss|Object ball|object… … Wikipedia**Rotation der Erde und Zeit**— Noch bis in die 30er Jahre des 20. Jahrhunderts glaubte man, dass die rotierende Erde einer sehr gleichmäßig gehenden Uhr entspräche, wenn man einmal von säkulären oder sehr langperiodischen Änderungen absieht. Sie diente daher als Normaluhr,… … Universal-Lexikon**Rotation of ammunition**— is a term used with reference to guns. Projectiles intended for R.M.L. (rifled muzzle loading) guns were at first fitted with a number of gun metal studs arranged around them in a spiral manner corresponding to the twist of rifling. This was… … Wikipedia