Faces Covering the Edges of a Graph

This problem is adapted from an abstract of a talk at the 3rd Slovenian International Conference in Graph Theory with the permission of Jose Caceres. The coauthors are L. Boza, J. Caceres, and A. Marquez.

Question: Given a natural number n and a surface S, what are the graphs which embed in S such that all edges lie on the boundary of one of n fixed faces?

Note that these graphs have an embedding which has a property about edges, instead of vertices as is the case in outerplanar, W-outerplanar, and generalized outerplanar graphs.

The above authors have an algorithm to construct the forbidden subgraphs for these graphs by using the forbidden multigraphs with an analogous property. They obtain the solution for n=1 and any surface, the cases n=2 and n=3 for the sphere, and the case n=2 for the torus. All other cases appear to be open. It is not known whether they considered nonorientable surfaces.

Submitted by: Daniel Sanders [I do not have his current address.]

Send comments to dan.archdeacon@uvm.edu

August, 1995