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

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.

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.

We have another 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 the second 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]).

[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. Providence, RI (1993) 109-130.

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