Planar Posets Have Dimension at Most Linear in Their Height

DOI10.1137/17M111300XMaRDI QIDQ4599767zbMATH OpenFDO

Authors Gwenaël Joret, Piotr Micek, Veit Wiechert

Publication date 4 January 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dimensionplanar graphposet

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: We prove that every planar poset $P$ of height $h$ has dimension at most $192h+96$. This improves on previous exponential bounds and is best possible up to a constant factor. We complement this result with a construction of planar posets of height $h$ and dimension at least $(4/3)h-2$.

Recommendations

• Dimension and height for posets with planar cover graphs
• Planar posets, dimension, breadth and the number of minimal elements
• Planar posets that are accessible from below have dimension at most 6
• Dimension and height for posets with planar cover graphs.
• Planarity and edge poset dimension
• Planar graphs and poset dimension
• Local dimension is unbounded for planar posets
• The dimension of posets with planar cover graphs.
• The Linear Extension Diameter of a Poset
• A note on the dimension of a poset

Cites work

• Dimension and height for posets with planar cover graphs.
• Minors and dimension
• On the dimension of partially ordered sets
• On the dimension of posets with cover graphs of treewidth 2
• Partial orders of dimension 2
• Sparsity and dimension
• The dimension of planar posets
• Topological minors of cover graphs and dimension
• Tree-width and dimension

Cited in

(15)

• Planar graphs and poset dimension
• Dimension of posets with planar cover graphs excluding two long incomparable chains
• Excluding a ladder
• Local dimension is unbounded for planar posets
• The dimension of posets with planar cover graphs.
• Dimension and height for posets with planar cover graphs.
• Planar posets that are accessible from below have dimension at most 6
• Dimension and height for posets with planar cover graphs
• Planar posets, dimension, breadth and the number of minimal elements
• Better bounds for poset dimension and boxicity
• Dimension is polynomial in height for posets with planar cover graphs
• Word-representable graphs: orientations, posets, and bounds
• Forcing the wheel
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• Adjacency posets of planar graphs

This page was built for publication: Planar Posets Have Dimension at Most Linear in Their Height

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