Graph minors. V. Excluding a planar graph
[For part I see the authors' paper ibid. 35, 39-61 (1983; Zbl 0521.05062), for part III see their paper ibid. 36, 49-64 (1984; Zbl 0548.05025), for part VI see ibid., 115-138 (1986; Zbl 0598.05042). See also their survey paper in Surveys in Combinatorics 1985, Pap. 10th Br. Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 153-171 (1985; Zbl 0568.05025).] Minors of graphs are obtained by contraction of subgraphs. A decomposition of a graph is a covering of both the vertices and edges by subgraphs, considered as a graph by connecting any two meeting pieces. It is shown that for each planar graph H there exists a number w such that any graph with no minor isomorphic to H admits a tree-decomposition with pieces of cardinality at most w. In fact this is proven first for H being a finite dimensional grid. As any planar graph is the minor of some such grid, the final result is obtained. Some consequences are as follows: There is no infinite family of graphs containing a planar one, and in which no graph is isomorphic to a minor of another one. Deciding whether a graph admits a fixed planar graph as a minor, is polynomially solvable. There is a characterization of planar graphs as those graphs which satisfy a property analogous to the one shown by Erdős and Posa for circuits.
- A characterisation of rigid circuit graphs
- A homology theory for spanning tress of a graph
- Ein Planaritaetskriterium für endliche Graphen
- From Matrices to Graphs
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. VII: Disjoint paths on a surface
- scientific article; zbMATH DE number 3603293 (Why is no real title available?)
- scientific article; zbMATH DE number 3332242 (Why is no real title available?)
- On Independent Circuits Contained in a Graph
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Linear connectivity forces large complete bipartite minors
- Graph operations characterizing rank-width
- A Menger-like property of tree-width: The finite case
- Grids and their minors
- On embedding graphs in trees
- Graph minors. X: Obstructions to tree-decomposition
- Decomposing infinite graphs
- Excluding infinite minors
- Canonical representations of partial 2- and 3-trees
- On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
- A partial k-arboretum of graphs with bounded treewidth
- Highly connected sets and the excluded grid theorem
- Obstruction set isolation for the gate matrix layout problem
- Quickly excluding a planar graph
- On search, decision, and the efficiency of polynomial-time algorithms
- A simpler proof of the excluded minor theorem for higher surfaces
- On interval routing schemes and treewidth
- Graph minors. XVI: Excluding a non-planar graph
- Clique-width of countable graphs: A compactness property.
- Induced and weak induced arboricities
- Binary constraint satisfaction problems defined by excluded topological minors
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Excluding a full grid minor
- \(K_4\)-expansions have the edge-Erdős-Pósa property
- Explicit linear kernels for packing problems
- A note on immersion minors and planarity
- A unified treatment of linked and lean tree-decompositions
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Graph minor hierarchies
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- On the structure of matrices avoiding interval-minor patterns
- Clique-sums, tree-decompositions and compactness
- Excluding any graph as a minor allows a low tree-width 2-coloring
- The monadic second-order logic of graphs. VIII: Orientations
- Directed tree-width
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Computing crossing numbers in quadratic time
- On tree-partitions of graphs
- On the excluded minor structure theorem for graphs of large tree-width
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Upper bounds to the clique width of graphs
- On the tree-width of even-hole-free graphs
- Packing and covering immersions in 4-edge-connected graphs
- A Menger-like property of tree-cut width
- Reducing graph transversals via edge contractions
- Fractal dimension and lower bounds for geometric problems
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- Critical properties and complexity measures of read-once Boolean functions
- On Tseitin formulas, read-once branching programs and treewidth
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- Notes on graph product structure theory
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Excluding a ladder
- Additive non-approximability of chromatic number in proper minor-closed classes
- The grid theorem for vertex-minors
- Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
- Hereditary classes of graphs: a parametric approach
- On the impact of treewidth in the computational complexity of freezing dynamics
- Uncountably many minimal hereditary classes of graphs of unbounded clique-width
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- Tree-width dichotomy
- On objects dual to tree-cut decompositions
- Erdős-Pósa property of chordless cycles and its applications
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Tangle-tree duality in abstract separation systems
- Towards tight(er) bounds for the excluded grid theorem
- Sublinear search spaces for shortest path planning in grid and road networks
- Discrete optimization methods for group model selection in compressed sensing
- Jones' conjecture in subcubic graphs
- Packing \(A\)-paths of length zero modulo four
- Coloring temporal graphs
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Rabin's theorem in the concurrency setting: a conjecture
- Dichotomy results for fixed point counting in Boolean dynamical systems
- Tree-width and planar minors
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- Contraction obstructions for treewidth
- Packing cycles through prescribed vertices
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Treewidth of graphs with balanced separations
- On the maximum weight minimal separator
- In absence of long chordless cycles, large tree-width becomes a local phenomenon
- Structural tractability of enumerating CSP solutions
- On maximum independent set of categorical product and ultimate categorical ratios of graphs
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Minors in graphs of large _r-girth
- Packing and covering immersion-expansions of planar sub-cubic graphs
- Rank-width: algorithmic and structural results
- Recent techniques and results on the Erdős-Pósa property
- Layered separators in minor-closed graph classes with applications
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Infinitely many minimal classes of graphs of unbounded clique-width
- Certifying coloring algorithms for graphs without long induced paths
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- Obtaining a planar graph by vertex deletion
- The theory of guaranteed search on graphs
- Minimum degree conditions for vertex-disjoint even cycles in large graphs
- Square roots of minor closed graph classes
This page was built for publication: Graph minors. V. Excluding a planar graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079583)