On obstructions to small face covers in planar graphs
type: Item
instance of: scholarly article
title: On obstructions to small face covers in planar graphs
zbMATH Open document ID: 0781.05014
DOI: 10.1016/0095-8956(92)90040-5
published in: Journal of Combinatorial Theory. Series B
publication date: 1993-03-10T00:00:00Z
review text: 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.
reviewed by: Carsten Thomassen
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 130573
zbMATH Keywords: small face covers
zbMATH Keywords: plane graph
author: Daniel Bienstock
author: Nathaniel Dean
MaRDI profile type: Publication
full work available at URL: 0095-8956(92)90040-5
OpenAlex ID: W2002725847
cites work: Contractible edges in 3-connected graphs
cites work: On the Complexity of Covering Vertices by Faces in a Planar Graph
cites work: Linear-Time Test for Small Face Covers in any Fixed Surface
cites work: On Independent Circuits Contained in a Graph
cites work: Send-and-Split Method for Minimum-Concave-Cost Network Flows
cites work: Q3800059
cites work: Edge-disjoint paths in planar graphs
cites work: Q4198056
cites work: Untersuchungen über minimale \(n\)-fach zusammenhängende Graphen
cites work: Q3880849
cites work: Multicommodity flows in planar graphs
cites work: Graph minors. VI. Disjoint paths across a disc
cites work: Graph minors. VII: Disjoint paths on a surface
cites work: Graph minors. VIII: A Kuratowski theorem for general surfaces
cites work: Graph minors. XX: Wagner's conjecture
cites work: Disjoint paths in graphs
cites work: Disjoint homotopic paths and trees in a planar graph
cites work: Planarity and duality of finite and infinite graphs
description: scientific article; zbMATH DE number 130573