Face Covers and the Genus Problem for Apex Graphs

✍ Scribed by Bojan Mohar

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 198 KB
• Volume: 82
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2000.2026

✦ Synopsis

A graph G is an apex graph if it contains a vertex w such that G&w is a planar graph. It is easy to see that the genus g(G) of the apex graph G is bounded above by {&1, where { is the minimum 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) {Â160 (if G&w is 3-connected and {>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. Finally, it is shown that computing the genus of apex graphs is NP-hard.