Embeddings of graphs with no short noncontractible cycles (Q916669)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Embeddings of graphs with no short noncontractible cycles |
scientific article |
Statements
Embeddings of graphs with no short noncontractible cycles (English)
0 references
1990
0 references
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.
0 references
2-cell embeddings of connected graphs into closed orientable 2-manifolds
0 references
LEW
0 references
large edge width
0 references
LEW-embedding
0 references
minimum genus embedding
0 references
triangulations
0 references
0 references