Page 25 - 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. 25
k Ellingham: Construction Techniques for Graph Embeddings 13
All tracing algorithms give same result. In each case, resulting list of edges, destination
faces, and (outgoing) currents is called log of face.
In above examples, only one face, and edges uniquely identified by current, so can just
write log by listing currents:
8 9 7 4 −2 −9 −1 5 −3 −7 2 6 1 −8 −5 −6 −4 3
Current graphs with twisted edges
Principle for handling twisted edges: Twisted edges reverse whether we cross over in the
middle of the edge or not. To maintain consistency of rules about the way currents
act, when we go through a twist on an edge, current must reverse. Current reverses
in middle of edge, so twisted edges have same current going in opposite directions
on opposite ends.
Modifying standard tracing algorithm: When traverse a twisted edge, cross over in mid-
dle if vertices at ends have same direction, do not cross if vertices have opposite di-
rections.
Modifying clockwise- or anticlockwise-biased tracing algorithms: Always cross over in
middle of a twisted edge.
Dealing with lack of global orientation in derived graph: Unless base embedding is ac-
tually orientable, cannot trace faces in consistent way, using each edge once in each
direction. Give each vertex (f , t ) local (clockwise) rotation based on order edges en-
countered when tracing face f . In derived embedding suppose edge e = (f , t )(g , t a )
is derived from e with f , g on either side. Then e is twisted if both f and g trace e in
the same direction, untwisted if they trace it in opposite directions.
Example: For 13 current graph above, again just one face, edges uniquely identified by
currents. Log of face is
2 1∗ −1∗ −2 6 3∗ −3∗ −6 5 9∗ −9∗ −5
where ∗ denotes twisted edge in derived embedding.
Even with twisted edges derived embedding may be orientable (just as for nonorientable
voltage graphs). Will always be nonorientable if base graph is actually nonorientable
and current group has odd order.
All tracing algorithms give same result. In each case, resulting list of edges, destination
faces, and (outgoing) currents is called log of face.
In above examples, only one face, and edges uniquely identified by current, so can just
write log by listing currents:
8 9 7 4 −2 −9 −1 5 −3 −7 2 6 1 −8 −5 −6 −4 3
Current graphs with twisted edges
Principle for handling twisted edges: Twisted edges reverse whether we cross over in the
middle of the edge or not. To maintain consistency of rules about the way currents
act, when we go through a twist on an edge, current must reverse. Current reverses
in middle of edge, so twisted edges have same current going in opposite directions
on opposite ends.
Modifying standard tracing algorithm: When traverse a twisted edge, cross over in mid-
dle if vertices at ends have same direction, do not cross if vertices have opposite di-
rections.
Modifying clockwise- or anticlockwise-biased tracing algorithms: Always cross over in
middle of a twisted edge.
Dealing with lack of global orientation in derived graph: Unless base embedding is ac-
tually orientable, cannot trace faces in consistent way, using each edge once in each
direction. Give each vertex (f , t ) local (clockwise) rotation based on order edges en-
countered when tracing face f . In derived embedding suppose edge e = (f , t )(g , t a )
is derived from e with f , g on either side. Then e is twisted if both f and g trace e in
the same direction, untwisted if they trace it in opposite directions.
Example: For 13 current graph above, again just one face, edges uniquely identified by
currents. Log of face is
2 1∗ −1∗ −2 6 3∗ −3∗ −6 5 9∗ −9∗ −5
where ∗ denotes twisted edge in derived embedding.
Even with twisted edges derived embedding may be orientable (just as for nonorientable
voltage graphs). Will always be nonorientable if base graph is actually nonorientable
and current group has odd order.
