Graphs that Quadrangulate both the Torus and Klein Bottle



A quadrangulation of a surface S is an embedded graph G such that every face is of size 4. A diamond 2-curve is a curve C in S such that C intersects the quadrangulation in a pair of vertices {x,y}. Hence all but two points on the curve lie in the interior of two faces xayb, ycxd. If C is non-contractible, then it is called an essential diamond 2-curve.

If G quadrangulates S and has an essential diamond 2-curve, then it is easy to cut along this curve and re-imbed G so that it quadrangulates the Klein bottle (this embedding has faces xayd and xcyb). Nakamoto conjectures that this sufficient condition is necessary:

Conjecture:  If G is a graph that has a quadrangular embedding in the torus, then G has a quadrangular embedding in the Klein bottle if and only if the toroidal embedding has an essential diamond 2-curve.

Nakamoto [N] has proven this conjecture for 4-regular graphs.

References
:
 

[N] A. Nakamoto, Four-regular graphs which quadrangulate both the torus and the Klein bottle, (preprint).


Submitted by: Dan Archdeacon (with thanks to Atsuhiro Nakamoto nakamoto@edhs.ynu.ac.jp)

Send comments to dan.archdeacon@uvm.edu

November, 2003