Planar posets have dimension at most linear in their height

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$.

arXiv commentv2: Minor changes

References in corpus (2)

• Tree-width and dimension
• Minors and dimension

Cited by in corpus (3)

• Dimension of posets with planar cover graphs excluding two long incomparable chains
• Excluding a ladder
• Posets with $k$-outerplanar cover graphs have bounded dimension