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