{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T22:42:57Z","timestamp":1768689777173,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T00:00:00Z","timestamp":1521072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["648527"],"award-info":[{"award-number":["648527"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["SONATA 2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["SONATA 2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["PRELUDIUM 2013\/11\/N\/ST6\/02706"],"award-info":[{"award-number":["PRELUDIUM 2013\/11\/N\/ST6\/02706"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["START stipend"],"award-info":[{"award-number":["START stipend"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00453-018-0424-7","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T11:53:32Z","timestamp":1521114812000},"page":"557-588","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Cutwidth: Obstructions and Algorithmic Aspects"],"prefix":"10.1007","volume":"81","author":[{"given":"Archontia C.","family":"Giannopoulou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Florent","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":false,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"issue":"6","key":"424_CR1","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1017\/S0963548302005369","volume":"11","author":"P Bellenbaum","year":"2002","unstructured":"Bellenbaum, P., Diestel, R.: Two short proofs concerning tree-decompositions. Comb. Probab. Comput. 11(6), 541\u2013547 (2002)","journal-title":"Comb. Probab. Comput."},{"issue":"6","key":"424_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"424_CR3","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"424_CR4","doi-asserted-by":"crossref","unstructured":"Booth, H., Govindan, R., Langston, M.A., Ramachandramurthi, S.: Cutwidth approximation in linear time. In: Proceedings of the Second Great Lakes Symposium on VLSI, pp. 70\u201373. IEEE (1992)","DOI":"10.1109\/GLSV.1992.218363"},{"key":"424_CR5","unstructured":"Chatzidimitriou, D., Raymond, J., Sau, I., Thilikos, D.M.: An $${O}(\\log {OPT})$$ O ( log OPT ) -approximation for covering\/packing minor models of $$\\theta _r$$ \u03b8 r . In: Proceedings of WAOA 2015, pp. 122\u2013132 (2015). arXiv:1510.03945"},{"issue":"1","key":"424_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2010.10.003","volume":"101","author":"M Chudnovsky","year":"2011","unstructured":"Chudnovsky, M., Seymour, P.D.: A well-quasi-order for tournaments. J. Comb. Theory Ser. B 101(1), 47\u201353 (2011)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"424_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"key":"424_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar $${{\\cal{F}}}$$ F -deletion: approximation, kernelization and optimal FPT algorithms. In: Proceedings of FOCS 2012, pp. 470\u2013479. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"424_CR9","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: Faster computation of path-width. In: M\u00e4kinen, V., Puglisi, J.S., Salmela, L. (eds.) Combinatorial Algorithms: 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17\u201319, 2016, Proceedings, pp. 385\u2013396. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-44543-4_30"},{"key":"424_CR10","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, New York (1979)"},{"key":"424_CR11","doi-asserted-by":"crossref","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B 84(2), 270\u2013290 (2002). A correction is available at http:\/\/www.math.uwaterloo.ca\/~jfgeelen\/Publications\/bn-corr.pdf","DOI":"10.1006\/jctb.2001.2082"},{"key":"424_CR12","unstructured":"Giannopoulou, A.C., Pilipczuk, M., Thilikos, D.M., Raymond, J.F., Wrochna, M.: Linear kernels for edge deletion problems to immersion-closed graph classes (2016). arXiv:1609.07780"},{"issue":"1","key":"424_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(00)00080-7","volume":"230","author":"R Govindan","year":"2001","unstructured":"Govindan, R., Ramachandramurthi, S.: A weak immersion relation on graphs and its applications. Discrete Math. 230(1), 189\u2013206 (2001)","journal-title":"Discrete Math."},{"issue":"3","key":"424_CR14","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/110830514","volume":"26","author":"P Heggernes","year":"2012","unstructured":"Heggernes, P., van\u2019t Hof, P., Lokshtanov, D., Nederlof, J.: Computing the cutwidth of bipartite permutation graphs in linear time. SIAM J. Discrete Math. 26(3), 1008\u20131021 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"424_CR15","doi-asserted-by":"publisher","first-page":"1418","DOI":"10.1137\/080741197","volume":"25","author":"P Heggernes","year":"2011","unstructured":"Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs and threshold graphs. SIAM J. Discrete Math. 25(3), 1418\u20131437 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"424_CR16","unstructured":"Kant\u00e9, M.M., Kwon, O.: An upper bound on the size of obstructions for bounded linear rank-width (2014). arXiv:1412.6201"},{"issue":"1","key":"424_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(93)90171-J","volume":"43","author":"E Korach","year":"1993","unstructured":"Korach, E., Solel, N.: Tree-width, path-width, and cutwidth. Discrete Appl. Math. 43(1), 97\u2013101 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"424_CR18","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1006\/jctb.1997.1788","volume":"73","author":"J Lagergren","year":"1998","unstructured":"Lagergren, J.: Upper bounds on the size of obstructions and intertwines. J. Comb. Theory Ser. B 73(1), 7\u201340 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"424_CR19","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"FT Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"424_CR20","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jctb.2009.07.003","volume":"100","author":"N Robertson","year":"2010","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XXIII. Nash\u2013Williams\u2019 immersion conjecture. J. Comb. Theory Ser. B 100(2), 181\u2013205 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"424_CR21","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"issue":"1\u20133","key":"424_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(94)90092-2","volume":"127","author":"A Takahashi","year":"1994","unstructured":"Takahashi, A., Ueno, S., Kajitani, Y.: Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Math. 127(1\u20133), 293\u2013304 (1994). (Graph theory and applications (Hakone, 1990))","journal-title":"Discrete Math."},{"issue":"1","key":"424_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"424_CR24","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: algorithms for partial $$w$$ w -trees of bounded degree. J. Algorithms 56(1), 25\u201349 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"424_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(90)90130-R","volume":"48","author":"R Thomas","year":"1990","unstructured":"Thomas, R.: A Menger-like property of tree-width: the finite case. J. Comb. Theory Ser. B 48(1), 67\u201376 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"424_CR26","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2014.07.003","volume":"110","author":"P Wollan","year":"2015","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47\u201366 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"424_CR27","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM 32(4), 950\u2013988 (1985)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0424-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0424-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0424-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T20:29:16Z","timestamp":1751488156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0424-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,15]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["424"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0424-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,15]]},"assertion":[{"value":"13 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}