The variety of triangular embeddings of a graph in the projective plane
A 2-cell embedding of a simple 3-connected graph G in a fixed surface F is called triangular or a triangulation of F with the graph G if every its face has a 3-circuit as boundary. Two triangulations of F, both with one and the same graph G, are considered as (essentially) different provided there exists a 3-circuit of G that bounds a face in only one of them. Two triangulations are called isomorphic provided there exists a face-preserving bijection between their vertex sets. Classically, a theorem of Whitney implies that every planar 3-connected graph G is essentially one-way embeddable in the sphere. However such is not the case in the projective plane \(N_ 1\). The reviewed paper gives an example of three mutually different triangulations of \(N_ 1\), each with the same graph, two of which are isomorphic but not isomorphic to the third one. Assume a graph G admits a triangular embedding in \(N_ 1\). Denote by \(\tau =\tau (G)\) the total number of mutually different embeddings of G in \(N_ 1\). (If one embedding of a simple graph G in a surface is a triangulation, then it follows from Euler's formula that all embeddings of G in that surface are triangulations.) The spectrum of \(\tau\) is completely determined in the reviewed paper: \(\tau\in \{1,2,3,4,6,12\}\). The set of \(\tau\) mutually different triangulations of \(N_ 1\), each with the graph G, is partitioned into, say q, isomorphism classes. Denote their cardinalities by \(\tau_ n(n=1,...,q)\) in such a way that \(\tau_ 1\geq...\geq \tau_ q\). (Thus \(\tau_ 1+...+\tau_ q=\tau.)\) The variety of triangular embeddings of G in \(N_ 1\) is defined as \(var(G):=(\tau_ 1,...,\tau_ q)\). The main result of the paper reviewed is the complete spectrum of the tuple var(G): Theorem. Given an arbitrary triangulation of the projective plane, its graph G necessarily belongs to one of the following eleven series, accordingly to the value of the tuple var(G): \[ \begin{alignedat}{2}{12} & text{Series} &\quad& I &\quad& II &\quad& III &\quad& IV &\quad& V &\quad& VI &\quad& VII &\quad& VIII &\quad& IX &\quad& X &\quad& XI\\ \text{\hrule} & text{var} &\quad& (12) &\quad& (6) &\quad& (4) &\quad& (2,2) &\quad& (2,1,1) &\quad& (1,1,1,1) &\quad& (2,1) &\quad& (1,1,1) &\quad& (2) &\quad& (1,1) &\quad& (1)\end{alignedat} \] . Furthermore, Series I consists of the complete graph \(K_ 6\) only, and the other series are all infinite.
scientific article; zbMATH DE number 4191681