On obstructions to small face covers in planar graphs

DOI10.1016/0095-8956(92)90040-5zbMath0781.05014OpenAlexW2002725847MaRDI QIDQ1204479

Bienstock, Daniel, Nathaniel Dean

Publication date: 10 March 1993

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(92)90040-5

zbMATH Keywords

plane graphsmall face covers

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Covering contractible edges in 3‐connected graphs. I: Covers of size three are cutsets, Graph Minors and Parameterized Algorithm Design, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Outerplanar obstructions for a feedback vertex set, Obstruction sets for outer-cylindrical graphs, Outer-embeddability in certain pseudosurfaces arising from three spheres, Minor obstructions for apex-pseudoforests, Halin's theorem for cubic graphs on an annulus, Algorithms and obstructions for linear-width and related search parameters, Variations on a theme of Kuratowski, Face covers and the genus problem for apex graphs, Labeled \(K_{2,t}\) minors in plane graphs, Bounding the vertex cover number of a hypergraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Edge-disjoint paths in planar graphs
• Graph minors. VI. Disjoint paths across a disc
• Contractible edges in 3-connected graphs
• Graph minors. VII: Disjoint paths on a surface
• Planarity and duality of finite and infinite graphs
• Disjoint paths in graphs
• Multicommodity flows in planar graphs
• Disjoint homotopic paths and trees in a planar graph
• Untersuchungen über minimale \(n\)-fach zusammenhängende Graphen
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Linear-Time Test for Small Face Covers in any Fixed Surface
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• On Independent Circuits Contained in a Graph