Graph minors. V. Excluding a planar graph

DOI10.1016/0095-8956(86)90030-4zbMath0598.05055OpenAlexW2057826895WikidataQ56235113 ScholiaQ56235113MaRDI QIDQ1079583

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

zbMATH Keywords

planar graphs tree-width graph minors contraction of subgraphs Minors of graphs

Mathematics Subject Classification ID

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

Related Items

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Constant Congestion Brambles in Directed Graphs, Treewidth of Cartesian Products of Highly Connected Graphs, Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs, Adapting the Directed Grid Theorem into an FPT Algorithm, Characterising graphs with no subdivision of a wheel of bounded diameter, $k$-apices of minor-closed graph classes. I: Bounding the obstructions, On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments, Edge-treewidth: algorithmic and combinatorial properties, A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width, Approximating Pathwidth for Graphs of Small Treewidth, (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels, Even A‐cycles have the edge‐Erdős–Pósa property, First-order Logic with Connectivity Operators, The complexity of learning minor closed graph classes, Erdős–Pósa property of obstructions to interval graphs, Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs, Graphs of linear growth have bounded treewidth, Packing topological minors half‐integrally, Critical properties of bipartite permutation graphs, Excluding a planar matching minor in bipartite graphs, Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree, Induced subgraphs and tree decompositions. VII: Basic obstructions in $H$-free graphs, Parameterized Counting and Cayley Graph Expanders, Induced subgraphs and path decompositions, Rankings of graphs, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Induced subgraphs and tree decompositions V. one neighbor in a hole, The monadic second-order logic of graphs : Definable sets of finite graphs, Unnamed Item, A Tight Erdös--Pósa Function for Wheel Minors, Erdös--Pósa from Ball Packing, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, Excluded Forest Minors and the Erdős–Pósa Property, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations., Random graphs containing few disjoint excluded minors, Obstructions for Bounded Branch-depth in Matroids, Additive non-approximability of chromatic number in proper minor-closed classes, Unnamed Item, Lower bounds for strictly fundamental cycle bases in grid graphs, Unnamed Item, Unnamed Item, Unnamed Item, Parameterised complexity of model checking and satisfiability in propositional dependence logic, Subcritical Graph Classes Containing All Planar Graphs, Unnamed Item, Finding Detours is Fixed-Parameter Tractable, Elimination Distance to Bounded Degree on Planar Graphs, Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs, Modification to Planarity is Fixed Parameter Tractable, Lean Tree-Cut Decompositions: Obstructions and Algorithms, Nonrepetitive colorings of graphs, Nonrepetitive colorings of graphs, Packing Cycles Faster Than Erdos--Posa, Packing and Covering Induced Subdivisions, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Contraction-Bidimensionality of Geometric Intersection Graphs, Excluding a Substar and an Antisubstar, $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Faster 3-Coloring of Small-Diameter Graphs, Tree Pivot-Minors and Linear Rank-Width, Critical elements in combinatorially closed families of graph classes, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, The edge-Erdős-Pósa property, Edge-disjoint odd cycles in 4-edge-connected graphs, An edge variant of the Erdős-Pósa property, Fast partitioning $l$-apex graphs with applications to approximating maximum induced-subgraph problems, Obstruction set isolation for the gate matrix layout problem, Obstructions for partitioning into forests and outerplanar graphs, Induced and weak induced arboricities, Contraction bidimensionality of geometric intersection graphs, A polynomial time algorithm for strong edge coloring of partial $k$-trees, Computing crossing numbers in quadratic time, On search, decision, and the efficiency of polynomial-time algorithms, Parameterized dominating set problem in chordal graphs: Complexity and lower bound, Binary constraint satisfaction problems defined by excluded topological minors, Reduction rules for the maximum parsimony distance on phylogenetic trees, A Menger-like property of tree-width: The finite case, Grids and their minors, Coloring immersion-free graphs, On embedding graphs in trees, A simpler proof of the excluded minor theorem for higher surfaces, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Rooted grid minors, On tree-partitions of graphs, The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces, Algorithmic uses of the Feferman-Vaught theorem, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Some recent progress and applications in graph minor theory, The parameterized complexity of local search for TSP, more refined, On interval routing schemes and treewidth, On the excluded minor structure theorem for graphs of large tree-width, The edge-density for $K_{2,t}$ minors, Improved bounds on the planar branchwidth with respect to the largest grid minor size, $K_4$-expansions have the edge-Erdős-Pósa property, Immersion in four-edge-connected graphs, The disjoint paths problem in quadratic time, The Erdős-Pósa property for clique minors in highly connected graphs, The challenges of unbounded treewidth in parameterised subgraph counting problems, Linkless and flat embeddings in 3-space, An FPT 2-approximation for tree-cut decomposition, Graph minors. XVI: Excluding a non-planar graph, Local search: is brute-force avoidable?, \textsc{max-cut} and containment relations in graphs, Clique-width of countable graphs: A compactness property., Linear connectivity forces large complete bipartite minors: an alternative approach, The structure of graphs not admitting a fixed immersion, Implicit branching and parameterized partial cover problems, Minimal classes of graphs of unbounded clique-width, Polynomial treewidth forces a large grid-like-minor, Graph minors. X: Obstructions to tree-decomposition, Upper bounds to the clique width of graphs, Algebraically grid-like graphs have large tree-width, Thue type problems for graphs, points, and numbers, Nonrepetitive colorings of graphs of bounded tree-width, On the tree-width of even-hole-free graphs, Explicit linear kernels for packing problems, Packing and covering immersions in 4-edge-connected graphs, Decomposing infinite graphs, Excluding infinite minors, A unified treatment of linked and lean tree-decompositions, Linearity of grid minors in treewidth with applications through bidimensionality, A new graph construction of unbounded clique-width, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Canonical representations of partial 2- and 3-trees, $K_{6}$ minors in large 6-connected graphs, A new proof of the flat wall theorem, An $O(\log \mathrm{OPT})$-approximation for covering and packing minor models of $\theta _r$, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, A Menger-like property of tree-cut width, Tree-width of graphs without a $3\times 3$ grid minor, Recent developments on graphs of bounded clique-width, Graph minor hierarchies, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Boundary properties of graphs for algorithmic graph problems, Crossing-critical graphs with large maximum degree, What is on his mind?, Upper domination: towards a dichotomy through boundary properties, Excluding a large theta graph, Reducing graph transversals via edge contractions, On the structure of matrices avoiding interval-minor patterns, 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, Graphs without large apples and the maximum weight independent set problem, On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs, A relaxation of the directed disjoint paths problem: a global congestion metric helps, Clique-sums, tree-decompositions and compactness, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Linear connectivity forces large complete bipartite minors, A partial k-arboretum of graphs with bounded treewidth, Graph operations characterizing rank-width, Excluding any graph as a minor allows a low tree-width 2-coloring, Graphs without two vertex-disjoint $S$-cycles, The monadic second-order logic of graphs. VIII: Orientations, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, Excluding a ladder, Directed tree-width, Highly connected sets and the excluded grid theorem, Additive non-approximability of chromatic number in proper minor-closed classes, The grid theorem for vertex-minors, The structure of the models of decidable monadic theories of graphs, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Adapting the directed grid theorem into an \textsf{FPT} algorithm, Uniform Kernelization Complexity of Hitting Forbidden Minors, Tree-width dichotomy, Forcing a K_r minor by high external connectivity, Towards the Graph Minor Theorems for Directed Graphs, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH, Packing and Covering Immersion Models of Planar Subcubic Graphs, Excluding a planar graph from $\mathrm{GF}(q)$-representable matroids, Graph minors. IV: Tree-width and well-quasi-ordering, Graph minors. VIII: A Kuratowski theorem for general surfaces, A Tighter Erdős-Pósa Function for Long Cycles, Frames, $A$-Paths, and the Erdös--Pósa Property, Minors in graphs of large $\theta_r$-girth, Packing and covering immersion-expansions of planar sub-cubic graphs, On objects dual to tree-cut decompositions, Rank-width: algorithmic and structural results, Recent techniques and results on the Erdős-Pósa property, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Steiner trees for hereditary graph classes: a treewidth perspective, Seymour's conjecture on 2-connected graphs of large pathwidth, Computing the largest bond and the maximum connected cut of a graph, Layered separators in minor-closed graph classes with applications, Clustered variants of Hajós' conjecture, Erdös-Pósa Property of Obstructions to Interval Graphs, Approximation Algorithms for Euler Genus and Related Problems, 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, Large Induced Subgraphs via Triangulations and CMSO, $K_{6}$ minors in 6-connected graphs of bounded tree-width, An Improved Algorithm for Finding Cycles Through Elements, Improved kernels for tracking paths, Low Polynomial Exclusion of Planar Graph Patterns, Efficient First-Order Model-Checking Using Short Labels, Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, Shortcutting Planar Digraphs, Obtaining a planar graph by vertex deletion, Erdős-Pósa property of chordless cycles and its applications, Polynomial kernels for hitting forbidden minors under structural parameterizations, Grid induced minor theorem for graphs of small degree, Graph theory. Abstracts from the workshop held January 2--8, 2022, The theory of guaranteed search on graphs, Minimum degree conditions for vertex-disjoint even cycles in large graphs, About the Domino Problem for Subshifts on Groups, Parameters Tied to Treewidth, Square roots of minor closed graph classes, Tangle-tree duality in abstract separation systems, Towards tight(er) bounds for the excluded grid theorem, Vertex-minor reductions can simulate edge contractions, 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, $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs, Sparse covers for planar graphs and graphs that exclude a fixed minor, Breaking the rhythm on graphs, Rabin's theorem in the concurrency setting: a conjecture, Planar graph bipartization in linear time, Dichotomy results for fixed point counting in Boolean dynamical systems, Tree-width and planar minors, Unnamed Item, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Obstructions to branch-decomposition of matroids, Turing kernelization for finding long paths in graph classes excluding a topological minor, The Maximum Independent Set Problem in Planar Graphs, Contraction obstructions for treewidth, Packing cycles through prescribed vertices, A model-theoretic characterisation of clique width, max-cut and Containment Relations in Graphs, Linear min-max relation between the treewidth of an $H$-minor-free graph and its largest grid minor, Nonrepetitive list colourings of paths, Graph minor theory, Unnamed Item, Strengthening Erdös-Pósa property for minor-closed graph classes, Cut Dominants and Forbidden Minors, Enumeration of Minimal Dominating Sets and Variants, Bidimensionality and Kernels, Recognizability in the Simply Typed Lambda-Calculus, Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs, Treewidth of graphs with balanced separations, FPT is characterized by useful obstruction sets, On the Parameterised Intractability of Monadic Second-Order Logic, Random Graphs with Few Disjoint Cycles, Rank-width and vertex-minors, Digraphs of Bounded Width, On the maximum weight minimal separator, In absence of long chordless cycles, large tree-width becomes a local phenomenon, Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation, Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles, Structural tractability of enumerating CSP solutions, Disjoint Paths—A Survey, Hereditary classes of graphs: a parametric approach, Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor, On maximum independent set of categorical product and ultimate categorical ratios of graphs, On the impact of treewidth in the computational complexity of freezing dynamics

Cites Work