Posets with k-outerplanar cover graphs have bounded dimension

MaRDI QIDQ6364063zbMATH OpenFDO

Authors Maximilian Gorsky, Michał T. Seweryn

Publication date 29 March 2021

Abstract: In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover graphs have bounded dimension. We generalise this result to posets with $k$-outerplanar cover graphs. Namely, we show that posets with $k$-outerplanar cover graph have dimension $mathcalO(k^3)$. As a consequence, we show that every poset with a planar cover graph and height $h$ has dimension $mathcalO(h^3)$. This improves the previously best known bound of $mathcalO(h^6)$ by Kozik, Micek and Trotter.

This page was built for publication: Posets with $k$-outerplanar cover graphs have bounded dimension

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