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
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• The structure of the models of decidable monadic theories of graphs
• Random graphs containing few disjoint excluded minors
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Graphs without large apples and the maximum weight independent set problem
• Linearity of grid minors in treewidth with applications through bidimensionality
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Boundary properties of graphs for algorithmic graph problems
• The edge-density for \(K_{2,t}\) minors
• The Maximum Independent Set Problem in Planar Graphs
• Algorithmic uses of the Feferman-Vaught theorem
• Minimal classes of graphs of unbounded clique-width
• The disjoint paths problem in quadratic time
• Linkless and flat embeddings in 3-space
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Graph minors. X: Obstructions to tree-decomposition
• Nonrepetitive colorings of graphs
• Recent developments on graphs of bounded clique-width
• Nonrepetitive colorings of graphs of bounded tree-width
• Excluded Forest Minors and the Erdős–Pósa Property
• Rankings of graphs
• Tree-width of graphs without a \(3\times 3\) grid minor
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Linear connectivity forces large complete bipartite minors
• Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
• A partial k-arboretum of graphs with bounded treewidth
• Polynomial treewidth forces a large grid-like-minor
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• The Erdős-Pósa property for clique minors in highly connected graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Implicit branching and parameterized partial cover problems
• Reduction rules for the maximum parsimony distance on phylogenetic trees
• \(K_{6}\) minors in large 6-connected graphs
• Clique-width of countable graphs: A compactness property.
• Max-Cut and containment relations in graphs
• Directed tree-width
• Tree-width and large grid minors in planar graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Contraction obstructions for treewidth
• Approximation algorithms for Euler genus and related problems
• Upper bounds to the clique width of graphs
• On the excluded minor structure theorem for graphs of large tree-width
• An edge variant of the Erdős-Pósa property
• Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
• Random graphs with few disjoint cycles

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)