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 (only showing first 100 items - show all)
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
This page was built for publication: Quickly excluding a planar graph
