LEW Embeddings of Weighted Graphs

The edge-width of an embedded graph is the length of the shortest cycle in the graph that is noncontractible in the surface. Thomassen [T] defined an LEW-embedding as one whose maximal face size is smaller than the edge-width of the embedding. He proved the following theorem.

Theorem: If Pi is an LEW-embedding of a 3-connected graph G, then the Pi-facial cycles are precisely those induced nonseparating cycles of G whose length is smaller than the edge-width of Pi. Any other embedding of G has strictly larger Euler genus. In particular any 3-connected graph has at most one LEW-embedding.

A proof similar to that of the above theorem gives the following generalization. Suppose that w assigns a positive real weight to each edge such that w(Q) < w(C) for every Pi-facial cycle Q and Pi-noncontractible cycle C. If G is 3-connected, then any other embedding of G has strictly larger Euler Genus than Pi.

It would be interesting to know to what extent this result can be used to characterize embeddings of minimal Euler genus (equivalently maximal Euler characteristic) that are unique. We propose the following.

Conjecture: Let G be a 3-connected Pi-embedded graph such that the face-width of Pi is at least 3. Then any other embedding of G has larger Euler genus if and only if there is a positive edge-weight function w from E(G) to the positive reals such that w(Q) < w(C) for every Pi-facial cycle Q and every Pi-noncontractible cycle C.

References:

[T] 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