Face covers and the genus problem for apex graphs
type: Item
instance of: scholarly article
title: Face covers and the genus problem for apex graphs
zbMATH Open document ID: 1025.05019
author: Bojan Mohar
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: 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.
reviewed by: Bojan Mohar
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1843763
zbMATH Keywords: planar graph
zbMATH Keywords: embedding
zbMATH Keywords: face cover
MaRDI profile type: Publication
full work available at URL: jctb.2000.2026
OpenAlex ID: W1974224894
cites work: On obstructions to small face covers in planar graphs
cites work: On the Complexity of Covering Vertices by Faces in a Planar Graph
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Q3757929
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Uniqueness and minimality of large face-width embeddings of graphs
cites work: Graphs on surfaces
cites work: Q4773723
cites work: The graph genus problem is NP-complete
cites work: Triangulating a surface with a prescribed graph
cites work: Q4156452
DOI: 10.1006/JCTB.2000.2026
Recommended article: Apex graphs with embeddings of face-width three
Recommended article: All minor-minimal apex obstructions with connectivity two
Recommended article: Vertex insertion approximates the crossing number of apex graphs
Recommended article: Computational complexity of the vertex cover problem in the class of planar triangulations
Recommended article: Face distributions of embeddings of complete graphs
Recommended article: Cliques, minors and apex graphs
Recommended article: Approximating the Crossing Number of Apex Graphs
Recommended article: Triangulating a surface with a prescribed graph
Recommended article: Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
Recommended article: Fundamentals of Computation Theory
description: scientific article; zbMATH DE number 1843763