scientific article; zbMATH DE number 4135963
[For the entire collection see Zbl 0688.00002.] A graph G is said to be \((p_ 1,p_ 2)\) biembeddable if there exist two subgraphs \(H_ 1\) and \(H_ 2\) of G with \(H_ 1\cup H_ 2=G\) so that, for \(i=1,2\), \(H_ i\) is embeddable in \(Sp_ i\) (the closed orientable 2-manifold of genus \(p_ i)\). A pair of such embeddings is a biembedding, and a biembedding is perfect if \(p_ 1=p_ 2\). The biembedding number N \((p_ 1,p_ 2)\) is the order of the smallest complete graph that has no \((p_ 1,p_ 2)\) biembedding. For example, since \(K_{13}\) has a perfect (1,1) biembedding, it follows that N (1,1)\(\geq 14\). (In fact, \(N(1,1)=14)\). Similar definitions exist for two nonorientable surfaces and for two surfaces of mixed orientability character. This paper presents a survey of known results and some conjectures concerning perfect biembeddings, such as: the minimum \(p_ 1\) such that \(K_ n\) has a \((p_ 1,p_ 1)\) biembedding is \(\lceil (n^ 2-13n+24)/24\rceil\). (This is known to be a lower bound, but only a few known examples of equality - such as for \(n=13\)- exist.)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3469113)