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
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
closed 2-cell embedding
0 references
circular embedding
0 references
strong embedding
0 references