Page 31 - 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. 31
k Ellingham: Construction Techniques for Graph Embeddings 19
1.5 Transition graphs
Comment on the name: In retrospect ‘transition graph’ is not a great name. Should really
be called ‘global rotation graphs’ or something like that: name comes from fact that
edges in rotation graph represent ‘transitions’ between two edges as we pass through
a vertex.
General idea: Given an embedded voltage graph, take rotation graph around each vertex
Rv . Now for each edge e from u to v identify the vertex of Ru corresponding to an
end of e with the vertex of Rv corresponding to the other end of e . Result is actually
medial graph of voltage graph. Add some information corresponding to embedding
of medial graph, edge twists, voltages.
Will not give formal definition. If desired, see [ESZ06].
Scope and usefulness: This is a general construction, equivalent to embedded voltage
graphs (or to current graphs).
We saw that current graphs were more convenient than voltage graphs for finding trian-
gular embeddings of complete graphs. Similarly, transition graphs are more conve-
nient for embeddings of regular complete bipartite graphs Km,m with control over
face sizes (usually want faces to be either 4-cycles or bamilton cycles). Play a key role
in determining genus of complete tripartite graphs.
Controlled embeddings of Km,m
Motivation: For complete tripartite graphs of form Km,m,n , may get min. genus embed-
ding from embedding of Km,m with
n hamilton cycle faces,
all other faces 4-cycles.
Can then add n new vertices in the hamilton cycle faces.
For joins of edgeless and complete graphs of form Km + Km , may get min. genus embed-
ding from embedding of Km,m with room in faces to add edges of a Km .
Structure of a transition graph: Construction has
group Γ, directed graph D, 0 = Z8 7 0
vertices (not edges) labelled by voltages in Γ,
edges partitioned into directed cycles,
each vertex traversed exactly twice by directed cycles, 6 1
vertices (not edges) may have twist (solid vertex •).
For embeddings of Km,m generally have 5 2
group Γ = m ,
exactly two directed cycles (solid, dashed).
Deriving the embedding: 43
Directed cycle → vertices indexed by Γ,
vertex → class of edges with given “slope”,
twisted vertex → twisted edges,
directed cycles show rotations.
1.5 Transition graphs
Comment on the name: In retrospect ‘transition graph’ is not a great name. Should really
be called ‘global rotation graphs’ or something like that: name comes from fact that
edges in rotation graph represent ‘transitions’ between two edges as we pass through
a vertex.
General idea: Given an embedded voltage graph, take rotation graph around each vertex
Rv . Now for each edge e from u to v identify the vertex of Ru corresponding to an
end of e with the vertex of Rv corresponding to the other end of e . Result is actually
medial graph of voltage graph. Add some information corresponding to embedding
of medial graph, edge twists, voltages.
Will not give formal definition. If desired, see [ESZ06].
Scope and usefulness: This is a general construction, equivalent to embedded voltage
graphs (or to current graphs).
We saw that current graphs were more convenient than voltage graphs for finding trian-
gular embeddings of complete graphs. Similarly, transition graphs are more conve-
nient for embeddings of regular complete bipartite graphs Km,m with control over
face sizes (usually want faces to be either 4-cycles or bamilton cycles). Play a key role
in determining genus of complete tripartite graphs.
Controlled embeddings of Km,m
Motivation: For complete tripartite graphs of form Km,m,n , may get min. genus embed-
ding from embedding of Km,m with
n hamilton cycle faces,
all other faces 4-cycles.
Can then add n new vertices in the hamilton cycle faces.
For joins of edgeless and complete graphs of form Km + Km , may get min. genus embed-
ding from embedding of Km,m with room in faces to add edges of a Km .
Structure of a transition graph: Construction has
group Γ, directed graph D, 0 = Z8 7 0
vertices (not edges) labelled by voltages in Γ,
edges partitioned into directed cycles,
each vertex traversed exactly twice by directed cycles, 6 1
vertices (not edges) may have twist (solid vertex •).
For embeddings of Km,m generally have 5 2
group Γ = m ,
exactly two directed cycles (solid, dashed).
Deriving the embedding: 43
Directed cycle → vertices indexed by Γ,
vertex → class of edges with given “slope”,
twisted vertex → twisted edges,
directed cycles show rotations.
