{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T20:13:57Z","timestamp":1790540037228,"version":"4.1.0"},"reference-count":61,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002910","name":"F\u00e9d\u00e9ration Wallonie-Bruxelles","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002910","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["418520"],"award-info":[{"award-number":["418520"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here \u201clinear size\u201d means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.<\/jats:p>","DOI":"10.1137\/17m1112637","type":"journal-article","created":{"date-parts":[[2018,4,10]],"date-time":"2018-04-10T11:42:06Z","timestamp":1523360526000},"page":"839-863","source":"Crossref","is-referenced-by-count":7,"title":["Orthogonal Tree Decompositions of Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergey","family":"Norin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":true,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10607"},{"key":"atypb3","unstructured":"M. J. Bannister, W. E. Devanny, V. Dujmovic\u0301, D. Eppstein, and D. R. Wood,\n                      Track Layouts, Layered Path Decompositions, and Leveled Planarity\n                      , preprint,https:\/\/arxiv.org\/abs\/1506.09145, 2015."},{"key":"atypb4","unstructured":"F. Barrera-Cruz, S. Felsner, T. Me\u0301sza\u0301ros, P. Micek, H. Smith, L. Taylor, and W. T. Trotter,\n                      Separating Tree-Chromatic Number from Path-Chromatic Number\n                      , preprint,https:\/\/arxiv.org\/abs\/1703.03973, 2017."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb6","first-page":"141","volume":"3","author":"Bodlaender H. L.","year":"1999","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0854"},{"key":"atypb8","unstructured":"B. Bolloba\u0301s.\n                      Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability\n                      , Cambridge University Press, Cambridge, UK, 1986."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(79)90071-2"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.12.004"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1178"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20237"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506148"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433410"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"atypb17","first-page":"840","author":"Demaine E. D.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.001"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00069"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062879"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00454"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.05.006"},{"key":"atypb23","unstructured":"Z. Dvor\u030ca\u0301k and S. Norin,\n                      Treewidth of Graphs with Balanced Separations\n                      , preprint,https:\/\/arxiv.org\/abs\/1408.3869, 2014."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/15M1017569"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"atypb26","first-page":"229","volume":"11","author":"Fa\u0301ry I.","year":"1948","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"atypb27","first-page":"P1","volume":"25","author":"Felsner S.","year":"2018","journal-title":"Electron. J. Combin."},{"key":"atypb28","first-page":"1563","author":"Fomin F. V.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990459"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000412"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Nes\u030cetr\u030cil,\n                      Graphs and Homomorphisms\n                      , Oxford University Press, Oxford, 2004,https:\/\/doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22121"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.001"},{"key":"atypb38","first-page":"153","author":"Kawarabayashi K.","year":"2010","journal-title":"Washington, DC"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90091-W"},{"key":"atypb40","unstructured":"J. R. Lee,\n                      Separators in Region Intersection Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/1608.01612, 2016."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000400"},{"key":"atypb42","first-page":"61","author":"Matous\u030cek J.","year":"2015","journal-title":"Pisa"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170210"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"J. Nes\u030cetr\u030cil and P. Ossona de Mendez,\n                      Sparsity: Graphs, Structures, and Algorithms\n                      , Algorithms and Combinatorics 28, Springer, Berlin, 2012,https:\/\/doi.org\/10.1007\/978-3-642-27875-4.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"atypb45","first-page":"221","author":"Norin S.","year":"2015","journal-title":"UK"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086610"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2891-4"},{"key":"atypb48","first-page":"87","author":"Reed B. A.","year":"1997","journal-title":"UK"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"atypb52","author":"Schaefer M.","year":"2014","journal-title":"Electron. J. Combin., DS21 ("},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00045-X"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.002"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"P. Seymour,\n                      Tree-chromatic number\n                      , J. Combin. Theory Ser. B, 116 (2016), pp. 229-237,https:\/\/doi.org\/10.1016\/j.jctb.2015.08.002.","DOI":"10.1016\/j.jctb.2015.08.002"},{"key":"atypb56","unstructured":"F. Shahrokhi,\n                      New representation results for planar graphs\n                      , in 29th European Workshop on Computational Geometry (EuroCG 2013), 2013, pp. 177-181; available online fromhttps:\/\/arxiv.org\/abs\/1502.06175."},{"key":"atypb57","unstructured":"K. Stavropoulos,\n                      On the Medianwidth of Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/1512.01104, 2015."},{"key":"atypb58","unstructured":"K. Stavropoulos,\n                      Cops, Robber and Medianwidth Parameters\n                      , preprint,https:\/\/arxiv.org\/abs\/1603.06871, 2016."},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(94)90021-3"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90061-4"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1112637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:18Z","timestamp":1787317518000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1112637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1112637"],"URL":"https:\/\/doi.org\/10.1137\/17m1112637","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}