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".]
[MR1] B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces, preprint.
[MR2] B. Mohar and N. Robertson,
essential circuits in toroidal maps, in
Graphs'' (W.T. Trotter, Ed.) Dimacs Series in Discrete Math. and
Theor. Comp. Sci.
Submitted by: Bojan Mohar,
Department of Mathematics,