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