Graph minors. V. Excluding a planar graph

DOI10.1016/0095-8956(86)90030-4zbMATH Open0598.05055DBLPjournals/jct/RobertsonS86OpenAlexW2057826895WikidataQ56235113 ScholiaQ56235113MaRDI QIDQ1079583FDOQ1079583

Authors: Neil Robertson, Paul Seymour 

Publication date: 1986

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(86)90030-4

Recommendations

• Graph minors. III. Planar tree-width
• Graph minors. XVI: Excluding a non-planar graph
• Quickly excluding a planar graph
• scientific article; zbMATH DE number 3906520
• Tree-width and large grid minors in planar graphs

zbMATH Keywords

graph minorsplanar graphstree-widthcontraction of subgraphsMinors of graphs

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. II. Algorithmic aspects of tree-width
• On Independent Circuits Contained in a Graph
• Title not available (Why is that?)
• A homology theory for spanning tress of a graph
• Graph minors. I. Excluding a forest
• Title not available (Why is that?)
• A characterisation of rigid circuit graphs
• Graph minors. VII: Disjoint paths on a surface
• Ein Planaritaetskriterium für endliche Graphen
• From Matrices to Graphs

Cited In (only showing first 100 items - show all)

• Treewidth of graphs with balanced separations
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Approximating Pathwidth for Graphs of Small Treewidth
• Tangle-tree duality in abstract separation systems
• Computing the largest bond and the maximum connected cut of a graph
• A Menger-like property of tree-cut width
• Hereditary classes of graphs: a parametric approach
• On Tseitin formulas, read-once branching programs and treewidth
• Adapting the directed grid theorem into an \textsf{FPT} algorithm
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Rabin's theorem in the concurrency setting: a conjecture
• A note on immersion minors and planarity
• A unified treatment of linked and lean tree-decompositions
• Title not available (Why is that?)
• About the domino problem for subshifts on groups
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Obstructions for bounded branch-depth in matroids
• Induced and weak induced arboricities
• Certifying coloring algorithms for graphs without long induced paths
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Packing and covering immersion models of planar subcubic graphs
• Binary constraint satisfaction problems defined by excluded topological minors
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Reducing graph transversals via edge contractions
• Fractal dimension and lower bounds for geometric problems
• Coloring temporal graphs
• Critical properties and complexity measures of read-once Boolean functions
• Packing and covering immersions in 4-edge-connected graphs
• Characterising graphs with no subdivision of a wheel of bounded diameter
• Seymour's conjecture on 2-connected graphs of large pathwidth
• Title not available (Why is that?)
• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• On the structure of matrices avoiding interval-minor patterns
• The theory of guaranteed search on graphs
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• \(\mathbb F\)-rank-width of (edge-colored) graphs
• \(K_4\)-expansions have the edge-Erdős-Pósa property
• On the maximum weight minimal separator
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• The excluded minors for isometric realizability in the plane
• Excluding a full grid minor
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Notes on graph product structure theory
• Packing and covering induced subdivisions
• Digraphs of bounded width
• On the impact of treewidth in the computational complexity of freezing dynamics
• Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
• Tree pivot-minors and linear rank-width
• A new proof of the flat wall theorem
• Layered separators in minor-closed graph classes with applications
• Obstructions for partitioning into forests and outerplanar graphs
• Contraction bidimensionality of geometric intersection graphs
• The edge-Erdős-Pósa property
• Clique-sums, tree-decompositions and compactness
• Induced subgraphs and path decompositions
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Graph minors and parameterized algorithm design
• Canonical representations of partial 2- and 3-trees
• \(K_4\)-subdivisions have the edge-Erdős-Pósa property
• The complexity of learning minor closed graph classes
• Graph minor hierarchies
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
• Title not available (Why is that?)
• Contraction-bidimensionality of geometric intersection graphs
• Square roots of minor closed graph classes
• Upper domination: towards a dichotomy through boundary properties
• Excluding a large theta graph
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
• \textsc{max-cut} and containment relations in graphs
• On tree-partitions of graphs
• Towards tight(er) bounds for the excluded grid theorem
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Lower bounds for strictly fundamental cycle bases in grid graphs
• Breaking the rhythm on graphs
• On the tree-width of even-hole-free graphs
• On interval routing schemes and treewidth
• Disjoint Paths—A Survey
• Some recent progress and applications in graph minor theory
• An Improved Algorithm for Finding Cycles Through Elements
• Graph operations characterizing rank-width
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• Parameters tied to treewidth
• A Menger-like property of tree-width: The finite case
• Rank-width: algorithmic and structural results
• Linear connectivity forces large complete bipartite minors: an alternative approach
• Nonrepetitive colorings of graphs
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• What is on his mind?
• Crossing-critical graphs with large maximum degree
• Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs
• Bipartite minors
• Unavoidable minors for graphs with large \(\ell_p\)-dimension
• Treewidth of Cartesian products of highly connected graphs
• Computing crossing numbers in quadratic time
• Title not available (Why is that?)

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)