**Planar
Graphs on Nonplanar Surfaces**

Suppose that *Pi* is an embedding of a 2-connected planar
graph *G*
in a nonplanar surface *S*. Let *k*
be an
integer. A simple closed curve *O* in *S* is a *k-curve*
if it
satisfies the following conditions:

(C1) *O*
intersects the graph *G*
in exactly *k* points and all these points are patch vertices of *G*,

(C2) *O* uses
only patch
vertices and patch faces of *G*,

(C3) *O *is *Pi*-noncontractible.

(See [MR1] for the definition of patch vertices and patch faces.)

Mohar and Robertson conjecture:

**Conjecture [MR1]:** *Suppose that* G *is a 2-connected
planar
graph that is* Pi-*embedded with face-width 2, and that* C_1,
C_2, C_3 *are
disjoint homotopic* Pi-*nonbounding**
cycles. Let *k *be the minimal number such that there exists a*
k-curve
*C* *that intersects each of* C_1, C_2, C_3
*exactly
once. Then *k *is equal to the maximal number* t *of pairwise disjoint cycles* C_1', ... ,
C_t' homotopic
to C_1.

Clearly, *k* is at least *t*. In [MR1] it is shown that
this conjecture
holds for the torus and the Klein bottle.
Examples
show that the requirement of this conjecture about existence of three
disjoint
cycles *C_1, C_2, C_3* cannot be entirely omitted (cf. [MR2]).

An earlier version of this page also
included another conjecture, which has been shown to be false. See "One problem about planar graphs on nonplanar
surfaces".]

**References: **

[MR1] B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces, preprint.

[MR2] B. Mohar and N. Robertson,
Disjoint
essential circuits in toroidal maps, in
``Planar
Graphs'' (W.T. Trotter, Ed.) Dimacs Series in Discrete Math. and
Theor. Comp. Sci.
**9**, Amer.
Math. Soc.

Submitted by: Bojan Mohar,
Department of Mathematics,

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

August, 1995