Finding the orientable genus of a graph is NP-complete in general. However, Fiedler, Huneke, Richter and Robertson [FHRR] showed that a graph embedded in the projective plane with face-width w has orientable genus [w/2], where [x] indicates the integer part of x. The embedding is constructed by cutting the projective planar embedding along a cycle achieving the face-width and using the [w/2] handles to reconnect the severed vertices and edges.

Using similar techniques Robertson and Thomas [RT] examined the orientable genus of graphs in the Klein bottle. They conjectured that if G is embedded in N_k, the nonorientable surface of genus k, with sufficiently large face-width, the following are equivalent:

The genus of G is at least g,

Every crossing-free blockage has order at least g,

Every blockage has order at least g.

(Cf. [RT] for definitions.)

Mohar [M] proposed a slightly different conjecture that might be off by a constant (depending on the genus) from the above conjecture of Robertson and Thomas. Suppose that G is embedded in N_k. Consider a crossing-free blockage F = {F_1,...,F_p} and cut the surface N_k along F_1,...,F_p. This results in a graph G' embedded in an orientable surface. Now each vertex v in both V(G) and one of the V(F_i) has two or more copies in G', and we add a new vertex v' and join it to all copies of v in G'. Call the resulting graph G'' and observe that the contraction of all new edge results in the original graph G. Now, the orientable embedding of G' defines local rotations of all vertices of G'' except for the new vertices v'. The minimum genus of an orientable embedding of G'' extending this partial embedding is called the genus order of the blockage F. Note that in the case no vertex of G is split into more than two vertices of G', the genus order coincides with the value conjectured by Robertson and Thomas, and that in general it is majorized by that value.

Conjecture: If G is embedded in a nonorientable surface with sufficiently large face-width, then the orientable genus of G is equal to the minimal genus order of a crossing-free blockage.

Mohar and Schrijver (personal communications) proved that this conjecture (and also the conjecture of Robertson and Thomas) holds up to a constant error term. More precisely, there is a function f from the natural numbers to themselves such that for any graph G embedded in N_k, then the orientable genus of G differs from the minimum order of a crossing-free blockage at most by f(k).

[FHRR] J. Fiedler, J.P. Huneke, R.B. Richter and N. Robertson, Computing the orientable genus of projective graphs, J. Graph Theory (to appear).

[RT] N. Robertson and R. Thomas, On the orientable genus of graphs embedded in the Klein bottle, J. Graph Theory 15 (1991) 407-419.

[M] B. Mohar, Face-width of embedded graphs, submitted.

Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia

Send comments to dan.archdeacon@uvm.edu and to bojan.mohar@uni-lj.si

August, 1995