On minimum-genus embeddings (Q1910582)

A minimum-genus surface of a graph \(G\) is a surface (orientable or nonorientable) of maximum Euler characteristic in which \(G\) can be imbedded. A surface \(S\) is said to have the genus strong embedding property if every 2-connected graph for which it is the minimum-genus surface has a closed 2-cell imbedding in \(S\). \textit{P. D. Seymour} [Graph theory and related topics, Proc. Conf. Honour W. T. Tutte, Waterloo/Ont. 1977, 341-355 (1979; Zbl 0465.05042)] conjectured that every surface has the genus strong imbedding property. The conjecture is true for the sphere (well known) and for the projective plane, see \textit{S. Negami} [J. Comb. Theory, Ser. B 44, No. 3, 276-299 (1988; Zbl 0609.05033)] and also \textit{N. Robertson} and \textit{R. Vitray} [Algorithms Comb. 9, 293-328 (1990; Zbl 0735.05032)]. The conjecture is false for the torus (\textit{N. H. Xuong}, Ph.D. Thesis, Grenoble, France, 1977). The present paper shows that the conjecture is false, for every other surface as well; thus the conjecture holds precisely for those surfaces of positive characteristic. Other related results are obtained.