Finding Separating Cycles in Embedded Graphs

The face-width of a graph G embedded in a surface S is the minimum number of points in C intersect G taken over all noncontractible C in S.

Question: What is the smallest value of n which implies that any embedding of face-width n in a surface of genus at least 2 must contain an essential separating polygon?

Zha and Zhao [ZZ] conjecture that face-width 3 suffices for the above. For orientable surfaces the value is known to lie between 3 and 6 [ZZ,BMR]. For nonorientable surfaces the value is less than or equal to 5 [ZZ]. It would be nice to have an example giving a lower bound of 3 for nonorientable surfaces.

Two related problems follow.

Prove or Disprove: In any face-width 2 embedding either the primal graph or the dual graph must contain an essential separating polygon.

Prove or Disprove: If a face-width 3 embedding of a graph contains an essential separating polygon, then the dual must also.

If the latter two conjectures are true, then the answer to the first question is n = 3.

Bojan Mohar proposes some related questions under the title ``Interpolation Conjectures on Separating Cycles in Embedded Graphs''. See also [M].

An unrelated and less precise question is related to other work I've been involved with.

Problem: Characterize classes of face-width 3 embeddings on a surface in which the number of faces does not exceed the number of vertices.

References:

[BMR] R. Brunet, B. Mohar, and R.B. Richter, On the homotopy of cycles in graph embeddings, preprint (1992).

[M] B. Mohar and N. Robertson, Disjoint essential cycles, in preparation.

[ZZ] X.Y. Zha and Y. Zhao, On nonnull separating circuits in embedded graphs, in ``Graph Structure Theory (Seattle, WA 1991)'', Contemp. Math. 147 American Math. Soc., Providence RI (1993) 349-363.

Submitted by: Rick Vitray, Math. Dept., Rollins College, Orlando, FL.

Send comments to dan.archdeacon@uvm.edu and to rick.vitray@rollins.edu

August, 1995