The genus problem for cubic graphs (Q1354116)

The NP-completeness of Ringel's problem of characterizing those graphs which triangulate some surface [Lect. Notes Math. 642, 455-475 (1978)] was established by the author [J. Comb. Theory, Ser. B 57, No. 2, 196-206 (1993; Zbl 0794.05025)]. In the present paper he considers the dual version, showing that the following problem is NP-complete. Given a cubic graph \(G\) and a natural number \(k\), is the genus of \(G\) at most \(k\)? The author observes that his proof extends to the nonorientable case and to \(r\)-regular graphs, for at least \(r=4\) and 5.