Posets with \(k\)-outerplanar cover graphs have bounded dimension

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 \(\mathcal{O}(k^3)\). As a consequen...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-05
Main Authors: Gorsky, Maximilian, Seweryn, Michał T
Format: Article
Language:English
Subjects:
Graphs
Set theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\mathcal{O}(k^3)\). As a consequence, we show that every poset with a planar cover graph and height \(h\) has dimension \(\mathcal{O}(h^3)\). This improves the previously best known bound of \(\mathcal{O}(h^6)\) by Kozik, Micek and Trotter.
ISSN:2331-8422