Face covers and the genus problem for apex graphs

A graph G is an apex graph if it contains a vertex w such that G - w is a p lanar graph. It is easy ro see that the genus g(G) of the apex graph G is b ounded above by tau - 1, where tau is the minimum face cover of the neighbo rs of w, taken over all planar embeddings of G - w. The main result of this paper is the linear lower bound g(G) greater than or equal to tau /160 (if 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 ve rtex cover is NP-hard For 2-connected cubic planar graphs. Finally, it is s hown that computing the genus or apex graphs is NP-hard. (C) 2001 Academic Press.