Quickly excluding a planar graph
From MaRDI portal
Publication:1338321
DOI10.1006/jctb.1994.1073zbMath0807.05023OpenAlexW2085348754MaRDI QIDQ1338321
Neil Robertson, Robin Thomas, P. D. Seymour
Publication date: 2 March 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1994.1073
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Towards the Graph Minor Theorems for Directed Graphs, Bivariate Complexity Analysis of Almost Forest Deletion, Unnamed Item, Erdös-Pósa Property of Obstructions to Interval Graphs, Approximation Algorithms for Euler Genus and Related Problems, Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Packing cycles in undirected group-labelled graphs, Edge-treewidth: algorithmic and combinatorial properties, Even-hole-free planar graphs have bounded treewidth, An Improved Algorithm for Finding Cycles Through Elements, Erdős–Pósa property of obstructions to interval graphs, Graphs of linear growth have bounded treewidth, Low Polynomial Exclusion of Planar Graph Patterns, Obtaining a Planar Graph by Vertex Deletion, Parameterized Counting and Cayley Graph Expanders, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Parameters Tied to Treewidth, Minor-Closed Graph Classes with Bounded Layered Pathwidth, On the Block Number of Graphs, Bounded Tree-Width and CSP-Related Problems, The size of an intertwine, 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, The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed, Unnamed Item, Some arithmetical restatements of the four color conjecture, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, Are There Any Good Digraph Width Measures?, Optimality program in segment and string graphs, Excluding a bipartite circle graph from line graphs, Large Independent Sets in Triangle-Free Planar Graphs, Unnamed Item, Strengthening Erdös-Pósa property for minor-closed graph classes, Finding Detours is Fixed-Parameter Tractable, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Decomposition of Map Graphs with Applications., On the Parameterised Intractability of Monadic Second-Order Logic, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Searching for a Visible, Lazy Fugitive, Contraction-Bidimensionality of Geometric Intersection Graphs, Planar Digraphs, Unnamed Item, Unnamed Item, Unnamed Item, Edge-disjoint odd cycles in 4-edge-connected graphs, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Contraction bidimensionality of geometric intersection graphs, A note on multiflows and treewidth, Triangle-free planar graphs with small independence number, Reduction rules for the maximum parsimony distance on phylogenetic trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Minors in large almost-5-connected non-planar graphs, Coloring immersion-free graphs, Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case, Quickly deciding minor-closed parameters in general graphs, On tree-partitions of graphs, Minors in graphs of large \(\theta_r\)-girth, Packing and covering immersion-expansions of planar sub-cubic graphs, Characterising \(k\)-connected sets in infinite graphs, Recent techniques and results on the Erdős-Pósa property, Sparse obstructions for minor-covering parameters, The obstructions of a minor-closed set of graphs defined by a context-free grammar, Some recent progress and applications in graph minor theory, Forbidding Kuratowski Graphs as Immersions, On interval routing schemes and treewidth, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Effective computation of immersion obstructions for unions of graph classes, Computing the best-case energy complexity of satisfying assignments in monotone circuits, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Untangling planar curves, Grid minors in damaged grids, Large Induced Subgraphs via Triangulations and CMSO, \(K_{6}\) minors in 6-connected graphs of bounded tree-width, Are there any good digraph width measures?, The disjoint paths problem in quadratic time, The complexity of two graph orientation problems, On the treewidth of toroidal grids, Linkless and flat embeddings in 3-space, Subexponential algorithms for partial cover problems, A note on planar graphs with large width parameters and small grid-minors, Obtaining a planar graph by vertex deletion, Packing \(A\)-paths of length zero modulo a prime, Graph minors. XVI: Excluding a non-planar graph, Contracting planar graphs to contractions of triangulations, Parameterized algorithms for stable matching with ties and incomplete lists, Packing cycles through prescribed vertices under modularity constraints, The theory of guaranteed search on graphs, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Subexponential parameterized algorithms, Faster parameterized algorithms for minor containment, Confronting intractability via parameters, Algorithms for finding an induced cycle in planar graphs, Packing cycles with modularity constraints, Treewidth lower bounds with brambles, Towards tight(er) bounds for the excluded grid theorem, Criticality for multicommodity flows, Spanners in sparse graphs, Implicit branching and parameterized partial cover problems, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Polynomial treewidth forces a large grid-like-minor, Graph minors. X: Obstructions to tree-decomposition, Succinct certification of monotone circuits, Nonrepetitive colorings of graphs of bounded tree-width, Packing \(A\)-paths of length zero modulo four, Packing and covering immersions in 4-edge-connected graphs, Excluding infinite minors, Linearity of grid minors in treewidth with applications through bidimensionality, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, \(K_{6}\) minors in large 6-connected graphs, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Fast minor testing in planar graphs, Parameterized complexity of the spanning tree congestion problem, Planar graph bipartization in linear time, Half-integral packing of odd cycles through prescribed vertices, Tree-width and planar minors, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, The complexity of counting homomorphisms seen from the other side, Succinct monotone circuit certification: planarity and parameterized complexity, Contraction obstructions for treewidth, A bound on the treewidth of planar even-hole-free graphs, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, Hitting Forbidden Minors: Approximation and Kernelization, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Fractal dimension and lower bounds for geometric problems, On tseitin formulas, read-once branching programs and treewidth, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Upper bounds on the size of obstructions and intertwines, Linear connectivity forces large complete bipartite minors, Graph minors. XXI. graphs with unique linkages, Tangles, tree-decompositions and grids in matroids, A partial k-arboretum of graphs with bounded treewidth, Treewidth of graphs with balanced separations, Induced packing of odd cycles in planar graphs, Excluding any graph as a minor allows a low tree-width 2-coloring, On planar graphs with large tree-width and small grid minors, Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs, Rank-width and vertex-minors, Bounded-depth Frege complexity of Tseitin formulas for all graphs, Minor-equivalence for infinite graphs, Minimizing the Oriented Diameter of a Planar Graph, Highly connected sets and the excluded grid theorem, Modifying a graph using vertex elimination, New limits of treewidth-based tractability in optimization
