**One Problem About Planar Graphs on Nonplanar
Surfaces (Solved)**

**On an earlier version of this problem
list we asked the following problem:**

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

**Conjecture [MR1]:** Suppose that *G* is a 2-connected
planar graph
that is *Pi*-embedded in an orientable
surface
of genus *g* with face-width 2. Then there is a set* C_1, ... , C_g* of pairwise noncrossing
homologically independent 2-curves.

**Gelasio**** Salizar [S]
reports (12/03) that he has disproved this conjecture.** Details are
to
follow.

I do not know if the following two related problems are still open:

A corresponding conjecture for nonorientable
surfaces *S* claims that there is a set *C = C_1, ... C_k* of homologically independent 2-curves
such that
twice the number of two-sided 2-curves plus the number of one-sided
2-curves in
*C* equals the nonorientable genus of
*S*,
i.e. 2 minus the Euler characteristic: 2-chi(S).

It may be true that even the following stronger property holds: If *C*
is any maximal set of pairwise-noncrossing
2-curves
(i.e., any 2-curve that is equivalent to no curve in *C* crosses
some
curve from *C*, then *C* contains a set of 2-curves
satisfying the
above conjecture.

A related problem is still open. See "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.

[S] G. Salazar, personal communication.

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.sit*

August, 1995. Modified December, 2003.