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
(i.e., any 2-curve that is equivalent to no curve in C crosses
curve from C, then C contains a set of 2-curves
A related problem is still open. See "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.
[S] G. Salazar, personal communication.
Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia
August, 1995. Modified December, 2003.