Face covers and the genus problem for apex graphs (Q1850536)

A graph \(G\) is an apex graph if it contains a vertex \(w\) such that \(G- w\) is a planar graph. Having an embedding of \(G- w\) in the plane and a subset \(U\) of its vertices, a face cover of \(U\) is a set of faces of \(G- w\) such that each vertex in \(U\) is contained on the boundary of one of these faces. It is easy to see that the genus \(g(G)\) of an apex graph \(G\) is bounded above by \(\tau- 1\), where \(\tau\) is the minimum number of faces in a face cover of the neighbors of \(w\), taken over all planar embeddings of \(G- w\). The main result of this paper is the linear lower bound \(g(G)\geq\tau/160\) in the case when \(G- w\) is 3-connected and \(\tau> 1\). It is also proved that the minimum face cover problem is NP-hard for planar triangulations and that the minimum vertex cover is NP-hard for 2-connected cubic planar graphs. This result answers a question of \textit{M. R. Garey}, \textit{D. S. Johnson} and \textit{L. Stockmeyer} [Theor. Comput. Sci. 1, 237-267 (1976; Zbl 0338.05120)]. Finally, it is shown that computing the genus of apex graphs is NP-hard. This settles a conjecture of Neil Robertson.