zbMATH — the first resource for mathematics

On obstructions to small face covers in planar graphs. (English) Zbl 0781.05014
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.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Ando, K; Enomoto, H; Saito, A, Contractible edges in 3-connected graphs, J. combin. theory ser. B, 42, 89-93, (1987) · Zbl 0611.05037
[2] Bienstock, D; Monma, C.L, On the complexity of covering vertices by faces in a planar graph, SIAM J. comput., 17, 53-76, (1988) · Zbl 0646.68085
[3] Bienstock, D, Linear-time test for small face covers in any fixed surface, SIAM J. comput., 19, 907-911, (1990) · Zbl 0711.68056
[4] Erdös, P; Pósa, L, On independent circuits contained in a graph, Canad. J. math, 17, 347-352, (1965) · Zbl 0129.39904
[5] Erickson, R.E; Monma, C.L; Vienott, A.F, Send-and-split method for minimum-concave-cost network flows, Math. oper. res., 12, 634-664, (1987) · Zbl 0667.90036
[6] Fellows, M; Hickling, F; Syslo, M, Topological parameterization and hard graph problems, (1986), University of New Mexico, Extended abstract · Zbl 0654.05027
[7] Frank, A, Edge-disjoint paths in planar graphs, J. combin. theory ser. B, 39, 164-178, (1985) · Zbl 0583.05036
[8] Garey, M.R; Johnson, D.S, ()
[9] Halin, R, Untersuchungen über minimale n-fach zusammenhängende graphen, Math. ann., 182, 175-188, (1969) · Zbl 0172.25804
[10] Harary, F, ()
[11] Lovász, L, ()
[12] Okamura, H; Seymour, P.D, Multicommodity flows in planar graphs, J. combin. theory ser. B, 31, 75-81, (1981) · Zbl 0465.90029
[13] Ota, K; Saito, A, Non-separating induced cyclin 3-connected graphs, (1986), manuscript
[14] Robertson, N; Seymour, P.D, Graph minors. VI. disjoint paths across a disk, J. combin. theory ser. B, 41, 115-138, (1986) · Zbl 0598.05042
[15] Robertson, N; Seymour, P.D, Graph minors. VII. disjoint paths on a surface, J. combin. theory ser. B, 45, 212-254, (1988) · Zbl 0658.05044
[16] Robertson, N; Seymour, P.D, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. combin. theory ser. B, 48, 255-288, (1990) · Zbl 0719.05033
[17] Robertson, N; Seymour, P.D, Graph minors. XV. Wagner’s conjecture, (1988), manuscript · Zbl 1061.05088
[18] Seymour, P.D, Disjoint paths in graphs, Discrete math., 29, 293-309, (1980) · Zbl 0457.05043
[19] \scP. D. Seymour, Personal communication, 1988.
[20] \scA. Schrijver, Disjoint homotopic paths and trees in a planar graph, Discrete Comput. Geom., to appear. · Zbl 0755.05033
[21] Steinitz, E, Polyheder und raumeinteilungen, Enzykl. math. wiss. 3 (geometrie), 12, 1-139, (1922), Part 3AB
[22] Thomassen, C, Planarity and duality of finite and infinite graphs, J. combin. theory ser. B, 29, 244-271, (1980) · Zbl 0441.05023
[23] Whitney, H, Two-isomorphic graphs, Trans. amer. math. soc., 34, 339-362, (1932) · JFM 58.0608.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.