{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T08:27:35Z","timestamp":1775464055557,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["259385 (DK)"],"award-info":[{"award-number":["259385 (DK)"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"name":"project 1M0545 of Ministry of Education of Czech Republic"},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Ne\u0161et\u0159il and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion.<\/jats:p>\n          <jats:p>More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition\/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Ne\u0161et\u0159il and Ossona de Mendez on the existence of low tree-depth colorings.<\/jats:p>","DOI":"10.1145\/2499483","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T15:29:17Z","timestamp":1382542157000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Testing first-order properties for subclasses of sparse graphs"],"prefix":"10.1145","volume":"60","author":[{"given":"Zden\u011bk","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[{"name":"Charles University in Prague, Czech Republic"}]},{"given":"Daniel","family":"Kr\u00e1l","sequence":"additional","affiliation":[{"name":"University of Warwick, United Kingdom"}]},{"given":"Robin","family":"Thomas","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}]}],"member":"320","published-online":{"date-parts":[[2013,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_2_1_3_1","unstructured":"Dawar A. and Kreutzer S. 2009. Parameterized complexity of first-order logic. In Electronic Colloquium on Computational Complexity TR09-131.  Dawar A. and Kreutzer S. 2009. Parameterized complexity of first-order logic. In Electronic Colloquium on Computational Complexity TR09-131."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11409-0_2"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of SODA'09","author":"Dvo"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.20"},{"key":"e_1_2_1_9_1","unstructured":"Dvo&rcaron&aacute;\u00e1k Z. Kr\u00e1l' D. and Thomas R. 2013. Three-coloring triangle-free graphs on surfaces VI. A linear-time algorithm.  Dvo&rcaron&aacute;\u00e1k Z. Kr\u00e1l' D. and Thomas R. 2013. Three-coloring triangle-free graphs on surfaces VI. A linear-time algorithm."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of SODA'95","author":"Eppstein D.","year":"1995"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_2_1_13_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Birkh\u00e4user.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Birkh\u00e4user."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_17_1","volume-title":"Model Theoretic Methods in Finite Combinatorics. AMS Contemporary Mathematics Series","volume":"558","author":"Grohe M."},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of IWPEC'08 (Victoria, Canada)","author":"Kreutzer S."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132575"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1502237"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0738-8"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499483","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:43Z","timestamp":1750235743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2499483"],"URL":"https:\/\/doi.org\/10.1145\/2499483","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}