In mathematics, a rotation map is a function that represents an undirected edge-labeled graph, where each vertex enumerates its outgoing neighbors. Rotation maps were first introduced by Reingold, Vadhan and Wigderson (“Entropy waves, the zig-zag graph product, and new constant-degree expanders”, 2002) in order to conveniently define the zig-zag product and prove its properties. Given a vertex
v
and an edge label
i
, the rotation map returns the
i
'th neighbor of
v
and the edge label that would lead back to
v
.
For a D-regular graph G, the rotation map
R
o
t
G
:
[
N
]
×
[
D
]
→
[
N
]
×
[
D
]
is defined as follows:
R
o
t
G
(
v
,
i
)
=
(
w
,
j
)
if the ith edge leaving v leads to w, and the jth edge leaving w leads to v.
From the definition we see that
R
o
t
G
is a permutation, and moreover
R
o
t
G
∘
R
o
t
G
is the identity map (
R
o
t
G
is an involution).
Special cases and properties
A rotation map is consistently labeled if all of the edges leaving each vertex are labeled in such a way that at each vertex, the labels of the incoming edges are all distinct. Every regular graph has some consistent labeling.
A rotation map is
π
-consistent if
∀
v
R
o
t
G
(
v
,
i
)
=
(
v
[
i
]
,
π
(
i
)
)
. From the definition, a
π
-consistent rotation map is consistently labeled.
