Graph minors. III. Planar tree-width
From MaRDI portal
Publication:799684
DOI10.1016/0095-8956(84)90013-3zbMATH Open0548.05025DBLPjournals/jct/RobertsonS84OpenAlexW2002722727WikidataQ56141697 ScholiaQ56141697MaRDI QIDQ799684FDOQ799684
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
Cites Work
Cited In (only showing first 100 items - show all)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- An existential locality theorem
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- Kernelization: new upper and lower bound techniques
- The structure of the models of decidable monadic theories of graphs
- Layered separators in minor-closed graph classes with applications
- The dag-width of directed graphs
- On self-duality of branchwidth in graphs of bounded genus
- The complexity of two graph orientation problems
- Positive Semidefinite Zero Forcing: Complexity and Lower Bounds
- On the hyperbolicity constant in graph minors
- Tree-width of hypergraphs and surface duality
- Title not available (Why is that?)
- Fixed-parameter algorithms for the cocoloring problem
- A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- On some graph densities in locally dense graphs
- Constant-degree graph expansions that preserve treewidth
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- A note on planar graphs with large width parameters and small grid-minors
- Linear connectivity forces large complete bipartite minors
- Graph minors. VII: Disjoint paths on a surface
- A partial k-arboretum of graphs with bounded treewidth
- A little statistical mechanics for the graph theorist
- Treewidth for graphs with small chordality
- Graph minors. V. Excluding a planar graph
- Datalog vs first-order logic
- An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Chordal embeddings of planar graphs
- Title not available (Why is that?)
- Posets with cover graph of pathwidth two have bounded dimension
- Approximate tree decompositions of planar graphs in linear time
- On the complexity of connection games
- Two approaches to Sidorenko's conjecture
- Graphs with magnetic Schrödinger operators of low corank
- Distance labeling scheme and split decomposition
- Directed tree-width
- Entanglement and the complexity of directed graphs
- Complexity of secure sets
- Surfaces, tree-width, clique-minors, and partitions
- Rank-width and tree-width of \(H\)-minor-free graphs
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Graph minors. I. Excluding a forest
- Some recent progress and applications in graph minor theory
- On the complexity of embedding planar graphs to minimize certain distance measures
- Parameterized complexity of satisfactory partition problem
- Fugitive-search games on graphs and related parameters
- Listing all potential maximal cliques of a graph
- Counting \(H-\)colorings of partial \(k-\)trees
- Structural tractability of enumerating CSP solutions
- Approximation of minimum weight spanners for sparse graphs
- Multiplicities of eigenvalues and tree-width of graphs
- Complexity of semi-stable and stage semantics in argumentation frameworks
- A model-theoretic characterisation of clique width
- Tree-width of graphs and surface duality
- Minimizing the oriented diameter of a planar graph
- Rank-width of random graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Weighted proper orientations of trees and graphs of bounded treewidth
- On the complexity of the disjoint paths problem
- On embedding graphs in trees
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Consequence-based and fixed-parameter tractable reasoning in description logics
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- On the advice complexity of the \(k\)-server problem under sparse metrics
- Dichotomies properties on computational complexity of \(S\)-packing coloring problems
- Large Induced Subgraphs via Triangulations and CMSO
- On compatibility and incompatibility of collections of unrooted phylogenetic trees
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Graph minors. IX: Disjoint crossed paths
- Lower bounds for positive semidefinite zero forcing and their applications
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minor theory
- Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
- On Algorithms Employing Treewidth for $L$-bounded Cut Problems
- Graph minors. IV: Tree-width and well-quasi-ordering
- Log-space algorithms for paths and matchings in \(k\)-trees
- The density maximization problem in graphs
- Methods for solving reasoning problems in abstract argumentation -- a survey
- The pagenumber of \(k\)-trees is \(O(k)\)
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
- 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
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)
