A note on strong embeddings of maximal planar graphs on non-orientable surfaces (Q5943373)

From MaRDI portal
scientific article; zbMATH DE number 1649220
Language Label Description Also known as
English
A note on strong embeddings of maximal planar graphs on non-orientable surfaces
scientific article; zbMATH DE number 1649220

    Statements

    A note on strong embeddings of maximal planar graphs on non-orientable surfaces (English)
    0 references
    0 references
    0 references
    29 March 2002
    0 references
    An embedding of a graph in a closed surface is said to be a closed 2-cell embedding if every face is a disk bounded by a simple circuit of the graph. In this paper, it is shown that every maximal planar graph of order \(n\) admits a strong 2-cell embedding in every nonorientable surface with genus at most \((n-2)/2\). The dual graph of such an embedding of genus \(g\) can be obtained from the dual graph \(G^*\) in the plane by applying the \(Y\Delta\) transformation on the set of \(g\) pairwise nonadjacent vertices of \(G^*\). This implies that strong 2-cell embeddings with planar dual graph exist for \(1 \leq g \leq (n-2)/2\).
    0 references
    0 references
    0 references
    closed 2-cell embedding
    0 references
    circular embedding
    0 references
    strong embedding
    0 references
    0 references