{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:31:05Z","timestamp":1775097065441,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520037","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"924-937","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Twin-width IV: ordered graphs and matrices"],"prefix":"10.1145","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"LIP, France \/ ENS Lyon, France"}]},{"given":"Ugo","family":"Giocanti","sequence":"additional","affiliation":[{"name":"LIP, France \/ ENS Lyon, France"}]},{"given":"Patrice","family":"Ossona de Mendez","sequence":"additional","affiliation":[{"name":"CAMS, France \/ CNRS, France"}]},{"given":"Pierre","family":"Simon","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"LIP, France \/ ENS Lyon, France"}]},{"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.10.001"},{"key":"e_1_3_2_1_3_1","volume-title":"Problems easy for tree-decomposable graphs (extended abstract)","author":"Arnborg Stefan","unstructured":"Stefan Arnborg , Jens Lagergren , and Detlef Seese . 1988. Problems easy for tree-decomposable graphs (extended abstract) . In Automata, Languages and Programming, Timo Lepist\u00f6 and Arto Salomaa (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 38\u201351. isbn:978-3-540-39291-0 Stefan Arnborg, Jens Lagergren, and Detlef Seese. 1988. Problems easy for tree-decomposable graphs (extended abstract). In Automata, Languages and Programming, Timo Lepist\u00f6 and Arto Salomaa (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 38\u201351. isbn:978-3-540-39291-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093870870"},{"key":"e_1_3_2_1_5_1","volume-title":"Topics in discrete mathematics","author":"Balogh J\u00f3zsef","unstructured":"J\u00f3zsef Balogh , B\u00e9la Bollob\u00e1s , and Robert Morris . 2006. Hereditary properties of ordered graphs . In Topics in discrete mathematics . Springer , 179\u2013213. J\u00f3zsef Balogh, B\u00e9la Bollob\u00e1s, and Robert Morris. 2006. Hereditary properties of ordered graphs. In Topics in discrete mathematics. Springer, 179\u2013213."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.05.004"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1952"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.02.004"},{"key":"e_1_3_2_1_9_1","volume-title":"St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant.","author":"Bonnet \u00c9douard","year":"2020","unstructured":"\u00c9douard Bonnet , Colin Geniet , Eun Jung Kim , St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2020 . Twin-width III: Max Independent Set and Coloring. CoRR , abs\/2007.14161 (2020), arxiv:2007.14161. arxiv:2007.14161 \u00c9douard Bonnet, Colin Geniet, Eun Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2020. Twin-width III: Max Independent Set and Coloring. CoRR, abs\/2007.14161 (2020), arxiv:2007.14161. arxiv:2007.14161"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.118"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"e_1_3_2_1_12_1","volume-title":"Sebastian Siebertz, and St\u00e9phan Thomass\u00e9.","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet , Jaroslav Nesetril , Patrice Ossona de Mendez , Sebastian Siebertz, and St\u00e9phan Thomass\u00e9. 2021 . Twin-width and permutations. CoRR , abs\/2102.06880 (2021), arxiv:2102.06880. arxiv:2102.06880 \u00c9douard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, and St\u00e9phan Thomass\u00e9. 2021. Twin-width and permutations. CoRR, abs\/2102.06880 (2021), arxiv:2102.06880. arxiv:2102.06880"},{"key":"e_1_3_2_1_13_1","volume-title":"First-Order Queries on Finite Abelian Groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL","author":"Bova Simone","year":"2015","unstructured":"Simone Bova and Barnaby Martin . 2015 . First-Order Queries on Finite Abelian Groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Simone Bova and Barnaby Martin. 2015. First-Order Queries on Finite Abelian Groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)."},{"key":"e_1_3_2_1_14_1","volume-title":"Laskowski","author":"Braunfeld Samuel","year":"2021","unstructured":"Samuel Braunfeld and Michael C . Laskowski . 2021 . Characterizations of monadic NIP. arxiv:math.LO\/2104.12989. Samuel Braunfeld and Michael C. Laskowski. 2021. Characterizations of monadic NIP. arxiv:math.LO\/2104.12989."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.04.003"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_1_20_1","volume-title":"First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS","author":"Downey Rodney G.","year":"1996","unstructured":"Rodney G. Downey , Michael R. Fellows , and Udayan Taylor . 1996. The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1] . In First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS 1996 , Auckland, New Zealand , December, 9-13, 1996, Douglas S. Bridges, Cristian S. Calude, Jeremy Gibbons, Steve Reeves, and Ian H. Witten (Eds.). Springer-Verlag , Singapore, 194\u2013213. Rodney G. Downey, Michael R. Fellows, and Udayan Taylor. 1996. The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1]. In First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS 1996, Auckland, New Zealand, December, 9-13, 1996, Douglas S. Bridges, Cristian S. Calude, Jeremy Gibbons, Steve Reeves, and Ian H. Witten (Eds.). Springer-Verlag, Singapore, 194\u2013213."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_22_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag Berlin Heidelberg. isbn:3540299521  J. Flum and M. Grohe. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag Berlin Heidelberg. isbn:3540299521"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.63"},{"key":"e_1_3_2_1_25_1","unstructured":"Jakub Gajarsk\u00fd Petr Hlinen\u00fd Daniel Lokshtanov Jan Obdrz\u00e1lek and M. S. Ramanujan. 2018. A New Perspective on FO Model Checking of Dense Graph Classes. CoRR abs\/1805.01823 (2018) arxiv:1805.01823. arxiv:1805.01823  Jakub Gajarsk\u00fd Petr Hlinen\u00fd Daniel Lokshtanov Jan Obdrz\u00e1lek and M. S. Ramanujan. 2018. A New Perspective on FO Model Checking of Dense Graph Classes. CoRR abs\/1805.01823 (2018) arxiv:1805.01823. arxiv:1805.01823"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935314"},{"key":"e_1_3_2_1_27_1","volume-title":"Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS","author":"Gajarsk\u00fd Jakub","year":"2018","unstructured":"Jakub Gajarsk\u00fd and Daniel Kr\u00e1\u013e . 2018 . Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Jakub Gajarsk\u00fd and Daniel Kr\u00e1\u013e. 2018. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.126"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.07.003"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.10.001"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Martin Klazar. 2000. The F\u00fcredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In Formal power series and algebraic combinatorics. 250\u2013255.  Martin Klazar. 2000. The F\u00fcredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In Formal power series and algebraic combinatorics. 250\u2013255.","DOI":"10.1007\/978-3-662-04166-6_22"},{"key":"e_1_3_2_1_33_1","article-title":"On Growth Rates of Permutations, Set Partitions","volume":"15","author":"Klazar Martin","year":"2008","unstructured":"Martin Klazar . 2008 . On Growth Rates of Permutations, Set Partitions , Ordered Graphs and Other Objects. Electron. J. Comb. , 15 , 1 (2008), http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r75.html Martin Klazar. 2008. On Growth Rates of Permutations, Set Partitions, Ordered Graphs and Other Objects. Electron. J. Comb., 15, 1 (2008), http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r75.html","journal-title":"Ordered Graphs and Other Objects. Electron. J. Comb."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:27)2012"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_2_1_36_1","volume-title":"Terry","author":"Laskowski Michael C.","year":"2020","unstructured":"Michael C. Laskowski and Caroline A . Terry . 2020 . Jumps in speeds of hereditary properties in finite relational languages. arxiv:math.CO\/1803.10575. Michael C. Laskowski and Caroline A. Terry. 2020. Jumps in speeds of hereditary properties in finite relational languages. arxiv:math.CO\/1803.10575."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90100-7"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0507350-7"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80203-8"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90015-5"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0098511"},{"key":"e_1_3_2_1_47_1","unstructured":"Pierre Simon. 2021. A note on stability and NIP in one variable. arxiv:math.LO\/2103.15799.  Pierre Simon. 2021. A note on stability and NIP in one variable. arxiv:math.LO\/2103.15799."},{"key":"e_1_3_2_1_48_1","volume-title":"Ordered graphs of bounded twin-width. CoRR, abs\/2102.06881","author":"Simon Pierre","year":"2021","unstructured":"Pierre Simon and Szymon Torunczyk . 2021. Ordered graphs of bounded twin-width. CoRR, abs\/2102.06881 ( 2021 ), arxiv:2102.06881. arxiv:2102.06881 Pierre Simon and Szymon Torunczyk. 2021. Ordered graphs of bounded twin-width. CoRR, abs\/2102.06881 (2021), arxiv:2102.06881. arxiv:2102.06881"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520037","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":48,"alternative-id":["10.1145\/3519935.3520037","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520037","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}