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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Biró, C., Keller, M.T., Young, S.J.: Posets with cover graph of pathwidth two have bounded dimension. Order, in press, doi:10.1007/s11083-015-9359-7. arXiv:1308.4877
Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3–4), 275–291 (2000)
Felsner, S., Trotter, W.T., Wiechert, V.: The dimension of posets with planar cover graphs. Graphs Combin. 31(4), 927–939 (2015)
Joret, G., Micek, P., Milans, K.G., Trotter, W.T., Walczak, B., Wang, R.: Tree-width and dimension. Combinatorica, in press, doi:10.1007/s00493-014-3081-8. arXiv:1301.5271
Joret, G, Micek, P, Wiechert, V: Sparsity and dimension. In: proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. arXiv:1507.01120, pp. 1804–1813 (2016)
Kelly, D.: On the dimension of partially ordered sets. Discret. Math. 35, 135–156 (1981)
Micek, P., Wiechert, V.: Topological minors of cover graphs and dimension. Submitted, arXiv:1504.07388
Streib, N., Trotter, W.T.: Dimension and height for posets with planar cover graphs. Eur. J. Combin. 35, 474–489 (2014)
Trotter, William T.: Combinatorics and partially ordered sets. Dimension theory. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (1992)
Trotter, W.T.: Partially ordered sets. In: Handbook of Combinatorics, vol. 1,2, pp. 433–480. Elsevier Science B.V., Amsterdam (1995)
Trotter, W.T., Jr., Moore, J.I., Jr.: The dimension of planar posets. J. Comb. Theory Ser. B 22(1), 54–67 (1977)
Walczak, B.: Minors and dimension. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. arXiv:1407.4066, pp. 1698–1707 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
G. Joret was supported by a DECRA Fellowship from the Australian Research Council.
P. Micek is supported by the Mobility Plus program from The Polish Ministry of Science and higher Education.
V. Wiechert is supported by the Deutsche Forschungsgemeinschaft within the research training group ‘Methods for Discrete Structures’ (GRK 1408).
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Joret, G., Micek, P., Trotter, W.T. et al. On the Dimension of Posets with Cover Graphs of Treewidth 2. Order 34, 185–234 (2017). https://doi.org/10.1007/s11083-016-9395-y
Received:
Accepted:
Published:
Issue date:
DOI: https://doi.org/10.1007/s11083-016-9395-y