On obstructions to small face covers in planar graphs (Q1204479)

It is shown that every plane graph contains a set \(V\) of vertices no two of which are on the same face and a set \(F\) of faces covering all vertices such that the cardinality of \(F\) is at most 27 times that of \(V\). The authors introduce the class \(F(k)\) of graphs which cannot be embedded in the plane with \(k\) or fewer faces and which are minor minimal with this property. It is shown that there exists a constant \(c\) such that every graph in \(F(k)\) has at most \(ck^ 3\) vertices.