Finding Embeddings of Large Face-Width



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

Question: Let k be a fixed integer at least 3. How difficult is it to decide if a given graph G admits an embedding of face-width k or more? If it does, can we find such an embedding in polynomial time? If k is at least 4 can we find such an embedding of G with minimal possible genus (or complexity) in polynomial time?

Carsten Thomassen [T1] has shown that it is NP-complete to determine the minimum genus embedding of a graph. However, a minimum face-width k embedding need not be of minimum genus.

The edge-width of the embedding is the length of the shortest noncontractible cycle in the graph. The edge-width is no smaller than the face-width. It may be larger as the noncontractible cycle can no longer cut across faces, but must instead follow paths on the face boundaries. The two parameters are the same for triangulations. Thomassen [T2] gives a polynomial-time algorithm for finding an LEW embedding if one exists. (An LEW or large-edge-width embedding is one where the edge-width is strictly larger than the maximum face size.)

References:

[T1] C. Thomassen, The graph genus problem is NP-complete, J. Algorithms 10 (1989) 568-576.

[T2] C. Thomassen, Embeddings of graphs with no short noncontractible cycles. J. Combin. Theory, Ser. B 48 (1990) 155-177.


Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia.

Send comments to dan.archdeacon@uvm.edu and to bojan.mohar@uni-lj.si

August, 1995