Embeddings of graphs with no short noncontractible cycles (Q916669): Difference between revisions

The author investigates 2-cell embeddings of connected graphs into closed orientable 2-manifolds which have the property that every noncontractible cycle has more edges than every face boundary. Such embeddings are called LEW (for large edge width) embeddings. He shows that every LEW-embedding of a graph G is on the surface of minimum genus for G. Moreover, if in addition G is 3-connected, then the embedding is unique (up to mirror- image). This generalizes the results of \textit{H. Whitney} [Am. J. Math. 55, 245-254 (1933; Zbl 0006.37005)] that a 3-connected planar graph has a unique embedding on the sphere. Polynomially bounded algorithms are obtained to: (1) find a shortest noncontractible cycle, for any graph embedding of positive genus; (2) describe an LEW-embedding of G or tell that no such exists, for any 3-connected graph G; (3) describe a minimum genus embedding of G or tell that G has no LEW-embedding, for any 2- connected graph G. Some of these results are refined for triangulations.