Graph minors. III. Planar tree-width
From MaRDI portal
Publication:799684
DOI10.1016/0095-8956(84)90013-3zbMath0548.05025DBLPjournals/jct/RobertsonS84OpenAlexW2002722727WikidataQ56141697 ScholiaQ56141697MaRDI QIDQ799684
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
Related Items (only showing first 100 items - show all)
Treewidth of the generalized Kneser graphs ⋮ A new approach on locally checkable problems ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The balanced satisfactory partition problem ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Even-power of cycles with many vertices are type 1 total colorable ⋮ An existential locality theorem ⋮ Datalog vs first-order logic ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Posets with cover graph of pathwidth two have bounded dimension ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ On the complexity of connection games ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Grids and their minors ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ A parameterized view on the complexity of dependence logic ⋮ On embedding graphs in trees ⋮ On the harmless set problem parameterized by treewidth ⋮ Graph minors. VII: Disjoint paths on a surface ⋮ On tree-partitions of graphs ⋮ Treewidth for graphs with small chordality ⋮ The Menger-like property of the three-width of infinite graphs ⋮ The tree-width of C ⋮ Some recent progress and applications in graph minor theory ⋮ Pushdown reachability with constant treewidth ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ The density maximization problem in graphs ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Entanglement and the complexity of directed graphs ⋮ Hypertree-depth and minors in hypergraphs ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Fugitive-search games on graphs and related parameters ⋮ Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs ⋮ Improved bounds on the planar branchwidth with respect to the largest grid minor size ⋮ Combinatorial problems on \(H\)-graphs ⋮ Tree-chromatic number ⋮ Sublinear separators, fragility and subexponential expansion ⋮ On self-duality of branchwidth in graphs of bounded genus ⋮ The complexity of two graph orientation problems ⋮ Interdiction problems on planar graphs ⋮ Tree-width of hypergraphs and surface duality ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Bounds for mean colour numbers of graphs ⋮ Constant-degree graph expansions that preserve treewidth ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ On fractional fragility rates of graph classes ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ A short note on the complexity of computing strong pathbreadth ⋮ Multidimensional bipartite trees ⋮ The dag-width of directed graphs ⋮ Chordal embeddings of planar graphs ⋮ Distance labeling scheme and split decomposition ⋮ On the complexity of core, kernel, and bargaining set ⋮ Clifford algebras meet tree decompositions ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ On the hyperbolicity constant in graph minors ⋮ Consequence-based and fixed-parameter tractable reasoning in description logics ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Efficiently enumerating minimal triangulations ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ A characterization of some graph classes using excluded minors ⋮ Lower bounds for positive semidefinite zero forcing and their applications ⋮ On classes of graphs with strongly sublinear separators ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Partitions versus sets: a case of duality ⋮ Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time ⋮ A little statistical mechanics for the graph theorist ⋮ Interval routing in reliability networks ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ On the complexity of embedding planar graphs to minimize certain distance measures ⋮ Complexity of secure sets ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ 2-connecting outerplanar graphs without blowing up the pathwidth ⋮ Universal augmentation schemes for network navigability ⋮ Graph minors. IX: Disjoint crossed paths ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ Linear connectivity forces large complete bipartite minors ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Nested cycles in large triangulations and crossing-critical graphs ⋮ Multiplicities of eigenvalues and tree-width of graphs ⋮ Excluding any graph as a minor allows a low tree-width 2-coloring ⋮ On the scramble number of graphs ⋮ Defensive alliances in graphs ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Compositions, decompositions, and conformability for total coloring on power of cycle graphs ⋮ Graph minors. I. Excluding a forest ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ Directed tree-width ⋮ Graphs with magnetic Schrödinger operators of low corank ⋮ A meta-theorem for distributed certification ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ The structure of the models of decidable monadic theories of graphs ⋮ Listing all potential maximal cliques of a graph ⋮ New limits of treewidth-based tractability in optimization
Cites Work
This page was built for publication: Graph minors. III. Planar tree-width
