Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-7039
Main Title: On the dimension of posets with cover graphs of treewidth 2
Author(s): Joret, Gwenael
Micek, Piotr
Trotter, William T.
Wang, Ruidong
Wiechert, Veit
Type: Article
Language Code: en
Abstract: In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276.
URI: https://depositonce.tu-berlin.de//handle/11303/7879
http://dx.doi.org/10.14279/depositonce-7039
Issue Date: 1-Jun-2016
Date Available: 28-May-2018
DDC Class: 510 Mathematik
Subject(s): poset
dimension
treewidth
License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Order : a journal on the theory of ordered sets and its applications
Publisher: Springer Science + Business Media B.V
Publisher Place: Dordrecht [u.a.]
Volume: 34
Issue: 2
Publisher DOI: 10.1007/s11083-016-9395-y
Page Start: 185
Page End: 234
EISSN: 1572-9273
Appears in Collections:FG Diskrete Mathematik » Publications

Files in This Item:
File Description SizeFormat 
10.1007%2Fs11083-016-9395-y.pdf2.1 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons