Abstract
Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. S. Baker: Approximation algorithms for NP-complete problems on planar graphs, in: Proc. 24th Annual Symposium on Foundations of Computer Science, 1983, 265–273; also in a journal version in: J. Assoc. Comput. Machin. 41 (1994), 153–180.
K. Baker, P. C. Fishburn and F. Roberts: Partial orders of dimension 2, interval orders and interval graphs, Networks 2 (1971), 11–28.
G. Di Battista, W.-P. Liu and I. Rival: Bipartite graphs, upward drawings, and planarity, Inform. Process. Lett. 36 (1990), 317–322.
C. Biró, M. T. Keller and S. J. Young: Posets with cover graphs of pathwidth two have bounded dimension, Order, in press and available on the ArXiv at 1308.4877v3.
H. L. Bodlaender: Planar graphs with bounded treewidth, Technical Report RUUCS-88-14, University of Utrecht, 1988.
G. R. Brightwell: On the complexity of diagram testing, Order 10 (1993), 297–303.
G. R. Brightwell and W. T. Trotter: The order dimension of convex polytopes, SIAM J. Discrete Math. 6 (1993), 230–245.
G. R. Brightwell and W. T. Trotter: The order dimension of planar maps, SIAM J. Discrete Math. 10 (1997), 515–528.
R. Diestel: Graph Theory, Graduate Texts in Mathematics, Vol. 173, Fourth Edition, Springer, 2010.
R. P. Dilworth: A decomposition theorem for partially ordered sets, Ann. Math. 41 (1950), 161–166.
B. Dushnik and E. W. Miller: Partially ordered sets, Amer. J. Math. 63 (1941), 600–610.
D. Eppstein: Diameter and treewidth in minor-closed graph families, Algorith-mica 27 (2000), 275–291.
S. Felsner: The order dimension of planar maps revisited, SIAM J. Discrete Math. 28 (2014), 1093–1101.
S. Felsner, C. M. Li and W. T. Trotter: Adjacency posets of planar graphs, Discrete Math. 310 (2010), 1097–1104.
S. Felsner, W. T. Trotter and V. Wiechert: The dimension of posets with planar cover graphs, Graphs Combin., in press and available on-line at Springer Japan 10.1007/s00373-014-1430-4.
P. C. Fishburn: Intransitive indifference with unequal indifference intervals, J. Math. Psych. 7 (1970), 144–149.
Z. Füredi, P. Hajnal, V. Röodl and W. T. Trotter: Interval orders and shift graphs, in: Sets, Graphs and Numbers: A Birthday Salute to Vera T. Sós and András Hajnal, Colloq. Math. Soc. János Bolyai, Vol. 60, North-Holland, 1992, 297–313.
T. Gallai: Transitiv orientierbare Graphen, Acta. Math. Acad. Sci. Hung. 18 (1967), 25–66.
A. Garg and R. Tamassia: On the computational complexity of upward and rectilinear planarity testing, SIAM J. Comput. 31 (2001), 601–625.
T. Hiraguchi: On the dimension of orders, Sci. Rep. Kanazawa Univ. 4 (1955), 1–20.
J. Hopcroft and R. E. Tarjan: Effcient planarity testing, J. Assoc. Comput. Machin. 21 (1974), 549–568.
G. Joret, P. Micek, W. T. Trotter, R. Wang and V. Wiechert: On the Dimension of Posets with Cover Graphs of Tree-width 2, submitted, available on the ArXiv at 1406.3397v2.
D. Kelly: On the dimension of partially ordered sets, Discrete Math. 35 (1981), 135–156.
L. Mirsky: A dual of Dilworth's decomposition theorem, Amer. Math. Monthly 78 (1971), 876–877.
J. I. Moore, Jr.: Graphs and partially ordered sets, Ph.D. Thesis, University of South Carolina, 1975.
J. Nešsetšril and V. Röodl: Complexity of diagrams, Order 3 (1987), 321–330. Corrigendum: Order 10 (1993), 393.
N. Robertson and P. D. Seymour: Graph minors. XX. Wagner's conjecture, J. Combin. Theory Ser. B 92 (2004), 325–357.
R. Stanley: personal communication.
N. Streib and W. T. Trotter: Dimension and height for posets with planar cover graphs, European J. Combin. 35 (2014), 474–489.
W. T. Trotter and J. I. Moore: The dimension of planar posets, J. Combin. Theory Ser. B 21 (1977), 51–67.
W. T. Trotter and R. Wang: Planar posets, dimension and the number of minimal elements, submitted.
K. Wagner: Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.
B. Walczak: Minors and dimension, in: Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, 1698–1707.
V. Wiechert: Planare Ordnungen und Dimension, B.Sc. Thesis, Technische Universität Berlin, 2012.
Author information
Authors and Affiliations
Corresponding author
Additional information
Bartosz Walczak was supported by Polish National Science Center grant 2011/03/N/ST6/03111.
Rights and permissions
About this article
Cite this article
Joret, G., Micek, P., Milans, K.G. et al. Tree-width and dimension. Combinatorica 36, 431–450 (2016). https://doi.org/10.1007/s00493-014-3081-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-014-3081-8