Strong embeddings of planar graphs on higher surfaces (Q1856781)

An embedding of a graph on a surface is called strong if each face boundary is a circuit. The authors discuss the upper bound for the genus of strong embeddings of 3-connected planar graphs on higher surfaces. They prove that each 3-connected planar graph \(G\) has a strong embedding on the non-orientable surface \(N_q\) with genus \(q = \Delta^*(G) - 2\), where \(\Delta^*(G)\) is the maximum face size of \(G\); this implies the result of \textit{R. B. Richter, P. D. Seymour} and \textit{J. Širáň} [Discrete Math. 126, 273-280 (1994; Zbl 0798.05020)]. Moreover, if \(\Delta^*(G)\) is an even number, then \(G\) admits a strong embedding on the orientable surface \(S_p\) with genus \(p = \frac{\Delta^*(G)-2}{2}\). Also, it is shown that the problem of finding the maximum genus \(q\) of the non-orientable surface \(N_q\) such that \(G\) has a strong embedding on \(N_q\) with the dual being planar is NP-hard in general.