Page 21 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 21
k Ellingham: Construction Techniques for Graph Embeddings 9
Voltage graphs
Basic construction: Start with base graph G , orient each edge e arbitrarily to get di-
rected edge e + in oriented graph G , reverse of e + is e −. (Oriented graph here refers
to putting a direction on each edge, nothing to do with surfaces.)
Have voltage group Γ (usually assumed to be finite), every edge assigned a weight or
voltage α(e +). Implicitly α(e −) = α(e )−1. Form derived graph G α as follows:
V (G α) = V (G ) × Γ.
For each e + from u to v in G with α(e +) = a , add an (oriented) edge (e +, g ) in
G α from (u , g ) to (v, g a ) for every g ∈ Γ. (Reverse of (e +, g ) is (e −, g a ).) Edge
directions can now be ignored.
Note: We multiply edge weights on right; could equally well define with edge weights
multiplying on left.
At this point we have just constructed a graph, no embeddings yet.
Remark: A Cayley graph is just a connected graph derived from a 1-vertex base voltage
graph. Since G has only one vertex, vertices of G α can be identified with elements of
Γ.
Embedded voltage graphs
Extension to embedded graphs: Suppose base graph G has 2-cell embedding Ψ in sur-
face. Describe using rotation projection. Construct 2-cell embedding of derived
graph with following additional rules:
Around each vertex (v, g ) of G α the edges follow the order of their images in G
(rotations are lifted).
Each edge in G α has the same type (untwisted or twisted) as its image in G .
Can actually describe in more abstract terms without using rotation projection, but
equivalent. Resulting derived embedding Ψα does not depend on specific rotation
projection. Objects in Ψ or G are said to lift to corresponding objects in Ψα or G α.
Voltage graphs
Basic construction: Start with base graph G , orient each edge e arbitrarily to get di-
rected edge e + in oriented graph G , reverse of e + is e −. (Oriented graph here refers
to putting a direction on each edge, nothing to do with surfaces.)
Have voltage group Γ (usually assumed to be finite), every edge assigned a weight or
voltage α(e +). Implicitly α(e −) = α(e )−1. Form derived graph G α as follows:
V (G α) = V (G ) × Γ.
For each e + from u to v in G with α(e +) = a , add an (oriented) edge (e +, g ) in
G α from (u , g ) to (v, g a ) for every g ∈ Γ. (Reverse of (e +, g ) is (e −, g a ).) Edge
directions can now be ignored.
Note: We multiply edge weights on right; could equally well define with edge weights
multiplying on left.
At this point we have just constructed a graph, no embeddings yet.
Remark: A Cayley graph is just a connected graph derived from a 1-vertex base voltage
graph. Since G has only one vertex, vertices of G α can be identified with elements of
Γ.
Embedded voltage graphs
Extension to embedded graphs: Suppose base graph G has 2-cell embedding Ψ in sur-
face. Describe using rotation projection. Construct 2-cell embedding of derived
graph with following additional rules:
Around each vertex (v, g ) of G α the edges follow the order of their images in G
(rotations are lifted).
Each edge in G α has the same type (untwisted or twisted) as its image in G .
Can actually describe in more abstract terms without using rotation projection, but
equivalent. Resulting derived embedding Ψα does not depend on specific rotation
projection. Objects in Ψ or G are said to lift to corresponding objects in Ψα or G α.
