Page 23 - 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. 23
k Ellingham: Construction Techniques for Graph Embeddings 11
1.3 Current graphs
Background: Current graphs were invented before voltage graphs, even though less in-
tuitive. Used in proof of Map Colour Theorem, determination of minimum genus of
complete graphs. Equivalent voltage graphs would have very few vertices, so it would
be very hard to keep track of where the edges go.
Current graphs are duals of voltage graphs (so apply to embedded voltage graphs). Faces
of current graph correspond to vertices in a voltage graph, and vice versa. However,
tricky to deal with duals when have edge weights: need to turn them 90◦, but which
way? Hard to decide without globally consistent orientation (which never have in
nonorientable case, and may not be given in orientable case).
See Gross and Tucker [GT] for general treatment. For simplicity we will restrict to current
graphs given as rotation projections in plane.
Current graphs without twisted edges (hence orientable)
Basic construction: We are given oriented graph with weights or currents on edges, from
current group Γ. For applications convenient to have two sorts of vertices (although
only really need one sort):
solid • = clockwise vertices,
open ◦ = anticlockwise vertices.
Obtain derived embedding as follows:
Vertices of derived embedding have form (f , t ) with f a face of the base graph and
t ∈ Γ. To get faces of base graph with globally consistent rotations, trace faces in
current graph in such a way that every edge is used once in each direction (trace
all clockwise, or all anticlockwise). Order of edges along face f specify rotation
around each vertex (f , t ) in derived embedding.
1.3 Current graphs
Background: Current graphs were invented before voltage graphs, even though less in-
tuitive. Used in proof of Map Colour Theorem, determination of minimum genus of
complete graphs. Equivalent voltage graphs would have very few vertices, so it would
be very hard to keep track of where the edges go.
Current graphs are duals of voltage graphs (so apply to embedded voltage graphs). Faces
of current graph correspond to vertices in a voltage graph, and vice versa. However,
tricky to deal with duals when have edge weights: need to turn them 90◦, but which
way? Hard to decide without globally consistent orientation (which never have in
nonorientable case, and may not be given in orientable case).
See Gross and Tucker [GT] for general treatment. For simplicity we will restrict to current
graphs given as rotation projections in plane.
Current graphs without twisted edges (hence orientable)
Basic construction: We are given oriented graph with weights or currents on edges, from
current group Γ. For applications convenient to have two sorts of vertices (although
only really need one sort):
solid • = clockwise vertices,
open ◦ = anticlockwise vertices.
Obtain derived embedding as follows:
Vertices of derived embedding have form (f , t ) with f a face of the base graph and
t ∈ Γ. To get faces of base graph with globally consistent rotations, trace faces in
current graph in such a way that every edge is used once in each direction (trace
all clockwise, or all anticlockwise). Order of edges along face f specify rotation
around each vertex (f , t ) in derived embedding.
