Orientable Genus of Graphs of Bounded Nonorientable Genus

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*,- The genus of
- Every crossing-free blockage has order at least
*g*,- Every crossing-free blockage has order at least
- Every blockage has order at least
*g*.- Every blockage has order at least

(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)*.

References:

[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