{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:54:25Z","timestamp":1787324065451,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Australian Government Research Training Program Scholarship"},{"name":"Australian Government Research Training Program Scholarship"},{"name":"Ontario Ministry of Research and Innovation"},{"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\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2018\/31\/G\/ST1\/03718"],"award-info":[{"award-number":["UMO-2018\/31\/G\/ST1\/03718"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212129"],"award-info":[{"award-number":["CCF-2212129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801\u2013808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton\u2013Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.<\/jats:p>","DOI":"10.1137\/23m1591773","type":"journal-article","created":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T04:30:27Z","timestamp":1720499427000},"page":"2095-2107","source":"Crossref","is-referenced-by-count":4,"title":["Product Structure Extension of the Alon\u2013Seymour\u2013Thomas Theorem"],"prefix":"10.1137","volume":"38","author":[{"given":"Marc","family":"Distel","sequence":"first","affiliation":[{"name":"School of Mathematics, Monash University, Melbourne, Victoria, Australia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[{"name":"School of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, ON, K1N 6N5, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of California, Irvine, Irvine, CA 92697-3425 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Hickingbotham","sequence":"additional","affiliation":[{"name":"School of Mathematics, Monash University, Melbourne, Victoria, Australia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7157-6694","authenticated-orcid":true,"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019Informatique, Universit\u00e9 libre de Bruxelles, Brussels, 1050, Belgium."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Jagiellonian University, Krak\u00f3w, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142 T.","family":"Seweryn","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019Informatique, Universit\u00e9 libre de Bruxelles, Brussels, 1050, Belgium."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":true,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[{"name":"School of Mathematics, Monash University, Melbourne, Victoria, Australia."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548323000457"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.001"},{"key":"ref5","first-page":"6","volume":"24","author":"Distel M.","year":"2022","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref6","first-page":"319","volume":"11","author":"Djidjev H. N.","year":"1985","journal-title":"Serdica"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000213"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"V. Dujmovi\u0107, R. Hickingbotham, J. Hodor, G. Joret, H. La, P. Micek, P. Morin, C. Rambaud, and D. R. Wood, The grid-minor theorem revisited, in Proceedings 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924), SIAM, 2024, pp. 1241\u20131245, https:\/\/doi.org\/10.1137\/1.9781611977912.48, arXiv:2307.02816.","DOI":"10.1137\/1.9781611977912.48"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3385731"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.05.006"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.03.004"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.12.007"},{"key":"ref13","unstructured":"Z. Dvo\u0159\u00e1k and D. R. Wood, Product Structure of Graph Classes with Strongly Sublinear Separators, preprint, arXiv:2208.10074, 2022."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.23008"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/22M1540296"},{"key":"ref18","unstructured":"F. Illingworth, A. Scott, and D. R. Wood, Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627, 2022; Trans. Amer. Math. Soc., to appear."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.03.026"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009140"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890"},{"key":"ref24","first-page":"85","volume-title":"Recent Advances in Algorithms and Combinatorics","volume":"11","author":"Reed B. A.","year":"2003"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.37236\/10614"},{"key":"ref28","volume":"23","author":"Wood D. R.","year":"2018","journal-title":"Electron. J. Combin."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1591773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:18:06Z","timestamp":1787321886000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1591773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,9]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/23M1591773"],"URL":"https:\/\/doi.org\/10.1137\/23m1591773","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,9]]}}}