Graph minors. III. Planar tree-width

DOI10.1016/0095-8956(84)90013-3zbMATH Open0548.05025DBLPjournals/jct/RobertsonS84OpenAlexW2002722727WikidataQ56141697 ScholiaQ56141697MaRDI QIDQ799684FDOQ799684

Neil Robertson, Paul Seymour

Publication date: 1984

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(84)90013-3

Recommendations

• Graph minors. V. Excluding a planar graph
• Tree-width and planar minors
• Tree-width and large grid minors in planar graphs
• Quickly excluding a planar graph
• Graph minors. IV: Tree-width and well-quasi-ordering

zbMATH Keywords

graph minorsplanar graphtree decompositiontree-width

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Cites Work

• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. I. Excluding a forest
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. IV: Tree-width and well-quasi-ordering

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

• Positive semidefinite zero forcing numbers of two classes of graphs
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Clifford algebras meet tree decompositions
• Beyond Outerplanarity
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
• Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• LP Formulations for Polynomial Optimization Problems
• On preprocessing techniques and their impact on propositional model counting
• An Improvement of Reed’s Treewidth Approximation
• Clustered 3-colouring graphs of bounded degree
• Title not available (Why is that?)
• Bidimensionality and Kernels
• Decompositions of triangle-dense graphs
• Graph Minors I: A Short Proof of the Path-width Theorem
• A new approach on locally checkable problems
• Succinct monotone circuit certification: planarity and parameterized complexity
• On classes of graphs with strongly sublinear separators
• Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
• Bundled Crossings Revisited
• A parameterized view on the complexity of dependence logic
• An improved planar graph product structure theorem
• On the harmless set problem parameterized by treewidth
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Coloring temporal graphs
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• Succinct certification of monotone circuits
• Hypertree-depth and minors in hypergraphs
• Helly-gap of a graph and vertex eccentricities
• An improvement of Reed's treewidth approximation
• Pushdown reachability with constant treewidth
• The theory of guaranteed search on graphs
• The tree-width of C
• Faster algorithms for quantitative verification in bounded treewidth graphs
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• On the scramble number of graphs
• Maximum flow under proportional delay constraint
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• New limits of treewidth-based tractability in optimization
• Cooperative games with overlapping coalitions: charting the tractability frontier
• On the parameterized complexity of the geodesic hull number
• On the satisfiability of quantum circuits of small treewidth
• Characteristic function games with restricted agent interactions: core-stability and coalition structures
• An FPT 2-approximation for tree-cut decomposition
• A short note on the complexity of computing strong pathbreadth
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Maximizing ink in partial edge drawings of \(k\)-plane graphs
• On the Satisfiability of Quantum Circuits of Small Treewidth
• Upper and lower degree-constrained graph orientation with minimum penalty
• Compositions, decompositions, and conformability for total coloring on power of cycle graphs
• A meta-theorem for distributed certification
• Even-power of cycles with many vertices are type 1 total colorable
• Self-avoiding walks and multiple context-free languages
• Some results on tree decomposition of graphs
• Treewidth of planar graphs: connections with duality
• Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
• Fugitive-search games on graphs and related parameters
• A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
• The balanced satisfactory partition problem
• Universal augmentation schemes for network navigability
• Excluding Subdivisions of Infinite Cliques
• Tree decomposition and discrete optimization problems: a survey
• Finite reflection groups and graph norms
• Partitions versus sets: a case of duality
• Bounds for mean colour numbers of graphs
• Combinatorial problems on \(H\)-graphs
• On the colored Tutte polynomial of a graph of bounded treewidth
• PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
• On fractional fragility rates of graph classes
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• The complexity of learning minor closed graph classes
• Circumference and Pathwidth of Highly Connected Graphs
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• The Menger-like property of the three-width of infinite graphs
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• On tree-partitions of graphs
• On the complexity of planning for agent teams and its implications for single agent planning
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Treewidth of the generalized Kneser graphs
• An analysis of the parameterized complexity of periodic timetabling
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• Graph Minors and Parameterized Algorithm Design
• Defensive alliances in graphs
• 2-connecting outerplanar graphs without blowing up the pathwidth
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
• Tree-chromatic number
• Sublinear separators, fragility and subexponential expansion
• Interdiction problems on planar graphs
• The \(k\)-strong induced arboricity of a graph
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• An Experimental Study of the Treewidth of Real-World Graph Data
• Burning Two Worlds
• Nested cycles in large triangulations and crossing-critical graphs
• Improved self-reduction algorithms for graphs with bounded treewidth
• Approximation algorithms for connected maximum cut and related problems
• Efficiently enumerating minimal triangulations
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

This page was built for publication: Graph minors. III. Planar tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799684)