Existence of polyhedral embeddings of graphs (Q5955209)

\textit{C. Thomassen} [J. Comb. Theory, Ser. B 57, No. 2, 196--206 (1993; Zbl 0794.05025)] proved that the decision problem whether a given cubic bipartite graph contains two compatible Hamilton cycles is NP-complete. Here, the decision problem ``Does a given graph \(G\) have a polyhedral embedding'' is proven to be NP-complete by constructing, from a given 2-connected cubic bipartite graph \(G_0\) a 6-connected graph \(G_1\) which has a polyhedral embedding if and only if \(G_0\) has two compatible Hamilton cycles. Moreover, if \(G_1\) has a polyhedral embedding, it also has an orientable polyhedral embedding.