Embeddings of graphs with no short noncontractible cycles (Q916669)

From MaRDI portal
Revision as of 09:53, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    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

    Identifiers