{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T21:40:46Z","timestamp":1777498846713,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T00:00:00Z","timestamp":1424822400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00493-014-3081-8","type":"journal-article","created":{"date-parts":[[2015,2,27]],"date-time":"2015-02-27T09:14:33Z","timestamp":1425028473000},"page":"431-450","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Tree-width and dimension"],"prefix":"10.1007","volume":"36","author":[{"given":"Gwena\u00ebl","family":"Joret","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin G.","family":"Milans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William T.","family":"Trotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruidong","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,25]]},"reference":[{"key":"3081_CR1","first-page":"153","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker: Approximation algorithms for NP-complete problems on planar graphs, in: Proc. 24th Annual Symposium on Foundations of Computer Science, 1983, 265\u2013273; also in a journal version in: J. Assoc. Comput. Machin. 41 (1994), 153\u2013180.","journal-title":"Proc. 24th Annual Symposium on Foundations of Computer Science"},{"key":"3081_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"K. Baker","year":"1971","unstructured":"K. Baker, P. C. Fishburn and F. Roberts: Partial orders of dimension 2, interval orders and interval graphs, Networks 2 (1971), 11\u201328.","journal-title":"Networks"},{"key":"3081_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(90)90045-Y","volume":"36","author":"G. D. Battista","year":"1990","unstructured":"G. Di Battista, W.-P. Liu and I. Rival: Bipartite graphs, upward drawings, and planarity, Inform. Process. Lett. 36 (1990), 317\u2013322.","journal-title":"Inform. Process. Lett"},{"key":"3081_CR4","unstructured":"C. Bir\u00f3, 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."},{"key":"3081_CR5","volume-title":"University of Utrecht","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender: Planar graphs with bounded treewidth, Technical Report RUUCS-88-14, University of Utrecht, 1988."},{"key":"3081_CR6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF01108825","volume":"10","author":"G. R. Brightwell","year":"1993","unstructured":"G. R. Brightwell: On the complexity of diagram testing, Order 10 (1993), 297\u2013303.","journal-title":"Order"},{"key":"3081_CR7","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0406018","volume":"6","author":"G. R. Brightwell","year":"1993","unstructured":"G. R. Brightwell and W. T. Trotter: The order dimension of convex polytopes, SIAM J. Discrete Math. 6 (1993), 230\u2013245.","journal-title":"SIAM J. Discrete Math"},{"key":"3081_CR8","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1137\/S0895480192238561","volume":"10","author":"G. R. Brightwell","year":"1997","unstructured":"G. R. Brightwell and W. T. Trotter: The order dimension of planar maps, SIAM J. Discrete Math. 10 (1997), 515\u2013528.","journal-title":"SIAM J. Discrete Math"},{"key":"3081_CR9","doi-asserted-by":"crossref","unstructured":"R. Diestel: Graph Theory, Graduate Texts in Mathematics, Vol. 173, Fourth Edition, Springer, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"3081_CR10","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"41","author":"R. P. Dilworth","year":"1950","unstructured":"R. P. Dilworth: A decomposition theorem for partially ordered sets, Ann. Math. 41 (1950), 161\u2013166.","journal-title":"Ann. Math"},{"key":"3081_CR11","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B. Dushnik","year":"1941","unstructured":"B. Dushnik and E. W. Miller: Partially ordered sets, Amer. J. Math. 63 (1941), 600\u2013610.","journal-title":"Amer. J. Math"},{"key":"3081_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"D. Eppstein: Diameter and treewidth in minor-closed graph families, Algorith-mica 27 (2000), 275\u2013291.","journal-title":"Algorith-mica"},{"key":"3081_CR13","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1137\/130945284","volume":"28","author":"S. Felsner","year":"2014","unstructured":"S. Felsner: The order dimension of planar maps revisited, SIAM J. Discrete Math. 28 (2014), 1093\u20131101.","journal-title":"SIAM J. Discrete Math"},{"key":"3081_CR14","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/j.disc.2009.11.005","volume":"310","author":"S. Felsner","year":"2010","unstructured":"S. Felsner, C. M. Li and W. T. Trotter: Adjacency posets of planar graphs, Discrete Math. 310 (2010), 1097\u20131104.","journal-title":"Discrete Math"},{"key":"3081_CR15","doi-asserted-by":"publisher","unstructured":"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 .","DOI":"10.1007\/s00373-014-1430-4"},{"key":"3081_CR16","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/0022-2496(70)90062-3","volume":"7","author":"P. C. Fishburn","year":"1970","unstructured":"P. C. Fishburn: Intransitive indifference with unequal indifference intervals, J. Math. Psych. 7 (1970), 144\u2013149.","journal-title":"J. Math. Psych"},{"key":"3081_CR17","first-page":"297","volume":"60","author":"Z. F\u00fcredi","year":"1992","unstructured":"Z. F\u00fcredi, P. Hajnal, V. R\u00f6odl and W. T. Trotter: Interval orders and shift graphs, in: Sets, Graphs and Numbers: A Birthday Salute to Vera T. S\u00f3s and Andr\u00e1s Hajnal, Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 60, North-Holland, 1992, 297\u2013313.","journal-title":"Sets, Graphs and Numbers: A Birthday Salute to Vera T. S\u00f3s and Andr\u00e1s Hajnal"},{"key":"3081_CR18","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"T. Gallai: Transitiv orientierbare Graphen, Acta. Math. Acad. Sci. Hung. 18 (1967), 25\u201366.","journal-title":"Acta. Math. Acad. Sci. Hung"},{"key":"3081_CR19","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A. Garg","year":"2001","unstructured":"A. Garg and R. Tamassia: On the computational complexity of upward and rectilinear planarity testing, SIAM J. Comput. 31 (2001), 601\u2013625.","journal-title":"SIAM J. Comput"},{"key":"3081_CR20","first-page":"1","volume":"4","author":"T. Hiraguchi","year":"1955","unstructured":"T. Hiraguchi: On the dimension of orders, Sci. Rep. Kanazawa Univ. 4 (1955), 1\u201320.","journal-title":"Sci. Rep. Kanazawa Univ"},{"key":"3081_CR21","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft and R. E. Tarjan: Effcient planarity testing, J. Assoc. Comput. Machin. 21 (1974), 549\u2013568.","journal-title":"J. Assoc. Comput. Machin"},{"key":"3081_CR22","unstructured":"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."},{"key":"3081_CR23","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0012-365X(81)90203-X","volume":"35","author":"D. Kelly","year":"1981","unstructured":"D. Kelly: On the dimension of partially ordered sets, Discrete Math. 35 (1981), 135\u2013156.","journal-title":"Discrete Math"},{"key":"3081_CR24","doi-asserted-by":"crossref","first-page":"876","DOI":"10.2307\/2316481","volume":"78","author":"L. Mirsky","year":"1971","unstructured":"L. Mirsky: A dual of Dilworth's decomposition theorem, Amer. Math. Monthly 78 (1971), 876\u2013877.","journal-title":"Amer. Math. Monthly"},{"key":"3081_CR25","volume-title":"Graphs and partially ordered sets","author":"J. I. Moore Jr","year":"1975","unstructured":"J. I. Moore, Jr.: Graphs and partially ordered sets, Ph.D. Thesis, University of South Carolina, 1975."},{"key":"3081_CR26","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF00340774","volume":"3","author":"J. Ne\u0161set\u0161ril","year":"1987","unstructured":"J. Ne\u0161set\u0161ril and V. R\u00f6odl: Complexity of diagrams, Order 3 (1987), 321\u2013330. Corrigendum: Order 10 (1993), 393.","journal-title":"Order"},{"key":"3081_CR27","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"N. Robertson and P. D. Seymour: Graph minors. XX. Wagner's conjecture, J. Combin. Theory Ser. B 92 (2004), 325\u2013357.","journal-title":"J. Combin. Theory Ser. B"},{"key":"3081_CR28","unstructured":"R. Stanley: personal communication."},{"key":"3081_CR29","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1016\/j.ejc.2013.06.017","volume":"35","author":"N. Streib","year":"2014","unstructured":"N. Streib and W. T. Trotter: Dimension and height for posets with planar cover graphs, European J. Combin. 35 (2014), 474\u2013489.","journal-title":"European J. Combin"},{"key":"3081_CR30","first-page":"51","volume":"21","author":"W. T. Trotter","year":"1977","unstructured":"W. T. Trotter and J. I. Moore: The dimension of planar posets, J. Combin. Theory Ser. B 21 (1977), 51\u201367.","journal-title":"J. Combin. Theory Ser. B"},{"key":"3081_CR31","unstructured":"W. T. Trotter and R. Wang: Planar posets, dimension and the number of minimal elements, submitted."},{"key":"3081_CR32","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"K. Wagner: \u00dcber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570\u2013590.","journal-title":"Math. Ann"},{"key":"3081_CR33","doi-asserted-by":"crossref","first-page":"1698","DOI":"10.1137\/1.9781611973730.113","volume-title":"Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B. Walczak","year":"2015","unstructured":"B. Walczak: Minors and dimension, in: Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, 1698\u20131707."},{"key":"3081_CR34","volume-title":"Planare Ordnungen und Dimension","author":"V. Wiechert","year":"2012","unstructured":"V. Wiechert: Planare Ordnungen und Dimension, B.Sc. Thesis, Technische Universit\u00e4t Berlin, 2012."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3081-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-3081-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3081-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T06:15:29Z","timestamp":1566368129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-3081-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,25]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["3081"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-3081-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,25]]}}}