Tree-width and dimension

DOI10.1007/S00493-014-3081-8zbMath1389.06004arXiv1301.5271OpenAlexW3101199164MaRDI QIDQ2400108

Gwenaël Joret, Bartosz Walczak, Kevin G. Milans, Piotr Micek, William T. jun. Trotter, Rui Dong Wang

Publication date: 25 August 2017

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.5271

zbMATH Keywords

posetdimensiontree-widthcover graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07) Distance in graphs (05C12)

Related Items (19)

Forcing posets with large dimension to contain large standard examples ⋮ The Parametric Closure Problem ⋮ Posets with cover graph of pathwidth two have bounded dimension ⋮ Planar posets, dimension, breadth and the number of minimal elements ⋮ Minors and dimension ⋮ Planar posets that are accessible from below have dimension at most 6 ⋮ On the dimension of posets with cover graphs of treewidth 2 ⋮ Trees and circle orders ⋮ Boolean dimension and local dimension ⋮ Planar Posets Have Dimension at Most Linear in Their Height ⋮ Dimension is polynomial in height for posets with planar cover graphs ⋮ Local dimension is unbounded for planar posets ⋮ Dimension of posets with planar cover graphs excluding two long incomparable chains ⋮ The graph of critical pairs of a crown ⋮ Dimension and matchings in comparability and incomparability graphs. ⋮ Better bounds for poset dimension and boxicity ⋮ Comparing Dushnik-Miller dimension, Boolean dimension and local dimension ⋮ Boolean dimension, components and blocks ⋮ Excluding a ladder

Cites Work

• Unnamed Item
• Posets with cover graph of pathwidth two have bounded dimension
• Planar posets, dimension, breadth and the number of minimal elements
• Graph minors. XX: Wagner's conjecture
• Bipartite graphs, upward drawings, and planarity
• Adjacency posets of planar graphs
• The dimension of planar posets
• Complexity of diagrams
• On the complexity of diagram testing
• Diameter and treewidth in minor-closed graph families
• On the dimension of posets with cover graphs of treewidth 2
• Dimension and height for posets with planar cover graphs.
• Intransitive indifference with unequal indifference intervals
• A decomposition theorem for partially ordered sets
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• The Order Dimension of Planar Maps Revisited
• Efficient Planarity Testing
• The Order Dimension of Planar Maps
• The Order Dimension of Convex Polytopes
• Minors and Dimension
• Transitiv orientierbare Graphen
• Partial orders of dimension 2
• A Dual of Dilworth's Decomposition Theorem
• Partially Ordered Sets
• On the dimension of partially ordered sets

This page was built for publication: Tree-width and dimension