{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T04:14:47Z","timestamp":1728360887001},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T00:00:00Z","timestamp":1719187200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T00:00:00Z","timestamp":1719187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s00493-024-00110-6","type":"journal-article","created":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T13:02:44Z","timestamp":1719234164000},"page":"1115-1148","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Neighborhood Complexity of Planar Graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Gwena\u00ebl","family":"Joret","sequence":"first","affiliation":[]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,24]]},"reference":[{"issue":"4","key":"110_CR1","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1007\/s00224-010-9283-6","volume":"47","author":"I Abraham","year":"2010","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Wieder, U.: Strong-diameter decompositions of minor free graphs. Theory Comput. Syst. 47(4), 837\u2013855 (2010)","journal-title":"Theory Comput. Syst."},{"key":"110_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-57265-8","volume-title":"Proofs from the Book","author":"M Aigner","year":"2018","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from the Book, 6th edn. Springer, New York (2018)","edition":"6"},{"issue":"2","key":"110_CR3","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1137\/16M1097833","volume":"32","author":"L Beaudou","year":"2018","unstructured":"Beaudou, L., Dankelmann, P., Foucaud, F., Henning, M.A., Mary, A., Parreau, A.: Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension. SIAM J. Discret. Math. 32(2), 902\u2013918 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"110_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103772","volume":"115","author":"\u00c9 Bonnet","year":"2024","unstructured":"Bonnet, \u00c9., Foucaud, F., Lehtil\u00e4, T., Parreau, A.: Neighbourhood complexity of graphs of bounded twin-width. Eur. J. Comb. 115, 103772 (2024)","journal-title":"Eur. J. Comb."},{"issue":"11","key":"110_CR5","doi-asserted-by":"publisher","first-page":"3300","DOI":"10.1007\/s00453-022-00965-5","volume":"84","author":"\u00c9 Bonnet","year":"2022","unstructured":"Bonnet, \u00c9., Kim, E.J., Reinald, A., Thomass\u00e9, S., Watrigant, R.: Twin-width and polynomial kernels. Algorithmica 84(11), 3300\u20133337 (2022)","journal-title":"Algorithmica"},{"key":"110_CR6","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM 69(1) (2021)","DOI":"10.1145\/3486655"},{"key":"110_CR7","unstructured":"Bonnet, \u00c9., Kwon, O., Wood, D.R.: Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). arXiv:2202.11858 (2022)"},{"issue":"12","key":"110_CR8","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1016\/j.disc.2015.05.026","volume":"338","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Thomass\u00e9, S.: VC-dimension and Erdos-P\u00f3sa property. Discret. Math. 338(12), 2302\u20132317 (2015)","journal-title":"Discret. Math."},{"key":"110_CR9","doi-asserted-by":"crossref","unstructured":"Busch, C., LaFortune, R., Tirthapura, S.: Improved sparse covers for graphs excluding a fixed minor. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing\u2014PODC \u201907, Portland, Oregon, USA. ACM Press (2007)","DOI":"10.1145\/1281100.1281112"},{"key":"110_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00454-006-1260-0","volume":"37","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B., Vaxes, Y.: Covering planar graphs with a fixed number of balls. Discret. Comput. Geom. 37, 237\u2013244 (2007)","journal-title":"Discret. Comput. Geom."},{"issue":"5","key":"110_CR11","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/j.jcss.2009.10.005","volume":"76","author":"A Dawar","year":"2010","unstructured":"Dawar, A.: Homomorphism preservation on quasi-wide classes. J. Comput. Syst. Sci. 76(5), 324\u2013332 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"110_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer, New York (2017)","edition":"5"},{"issue":"4","key":"110_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3385731","volume":"67","author":"V Dujmovic","year":"2020","unstructured":"Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. J. ACM 67(4), 1\u201338 (2020)","journal-title":"J. ACM"},{"key":"110_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jctb.2023.03.004","volume":"162","author":"V Dujmovic","year":"2023","unstructured":"Dujmovic, V., Morin, P., Wood, D.R.: Graph product structure for non-minor-closed classes. J. Comb. Theory B 162, 34\u201367 (2023)","journal-title":"J. Comb. Theory B"},{"key":"110_CR15","unstructured":"Eickmeyer, K., Giannopoulou, A.C., Kreutzer, S., Kwon, O., Pilipczuk, M., Rabinovich, R., Siebertz, S.: Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.), 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume\u00a080 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 63:1\u201363:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"4","key":"110_CR16","doi-asserted-by":"publisher","first-page":"2467","DOI":"10.1137\/18M1168753","volume":"32","author":"M Grohe","year":"2018","unstructured":"Grohe, M., Kreutzer, S., Rabinovich, R., Siebertz, S., Stavropoulos, K.: Coloring and covering nowhere dense graphs. SIAM J. Discret. Math. 32(4), 2467\u20132481 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"110_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.ejc.2017.06.019","volume":"66","author":"J van den Heuvel","year":"2017","unstructured":"van den Heuvel, J., Ossona de Mendez, P., Quiroz, D., Rabinovich, R., Siebertz, S.: On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb. 66, 129\u2013144 (2017)","journal-title":"Eur. J. Comb."},{"key":"110_CR18","doi-asserted-by":"crossref","unstructured":"Li, J., Parter, M.: Planar diameter via metric compression. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 152\u2013163, New York, NY, USA, 2019. Association for Computing Machinery","DOI":"10.1145\/3313276.3316358"},{"key":"110_CR19","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)"},{"key":"110_CR20","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"110_CR21","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P.: Structural sparsity. Uspekhi Matematicheskikh Nauk 71(1):85\u2013116 (2016) (Russian Math. Surveys 71(1):79\u2013107)","DOI":"10.1070\/RM9688"},{"issue":"3","key":"110_CR22","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161etril","year":"2008","unstructured":"Ne\u0161etril, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Comb. 29(3), 760\u2013776 (2008)","journal-title":"Eur. J. Comb."},{"key":"110_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2021.06.002","volume":"151","author":"M Pilipczuk","year":"2021","unstructured":"Pilipczuk, M., Siebertz, S.: Polynomial bounds for centered colorings on proper minor-closed graph classes. J. Comb. Theory B 151, 111\u2013147 (2021)","journal-title":"J. Comb. Theory B"},{"key":"110_CR24","unstructured":"Przybyszewski, W.: VC-density and abstract cell decomposition for edge relation in graphs of bounded twin-width. arXiv:2202.04006 (2022)"},{"key":"110_CR25","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.ejc.2018.08.001","volume":"75","author":"F Reidl","year":"2019","unstructured":"Reidl, F., Villaamil, F.S., Stavropoulos, K.: Characterising bounded expansion by neighbourhood complexity. Eur. J. Comb. 75, 152\u2013168 (2019)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"110_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory A 13(1), 145\u2013147 (1972)","journal-title":"J. Comb. Theory A"},{"issue":"1","key":"110_CR27","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41(1), 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"key":"110_CR28","doi-asserted-by":"crossref","unstructured":"Soko\u0142owski, M.: Bounds on half graph orders in powers of sparse graphs. Electron. J. Comb. 30(2):P2.3 (2023)","DOI":"10.37236\/11063"},{"key":"110_CR29","doi-asserted-by":"crossref","unstructured":"Vapnik, V., Chervonenkis, A.: On the uniform convergence of relative frequencies of events to their probabilities. In: Measures of Complexity, pp. 11\u201330. Springer, New York (2015)","DOI":"10.1007\/978-3-319-21852-6_3"},{"key":"110_CR30","doi-asserted-by":"crossref","unstructured":"Zhu, X.: Colouring graphs with bounded generalized colouring number. Discret. Math. 309(18), 5562\u20135568 (2009)","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00110-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00110-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00110-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:08:59Z","timestamp":1728302939000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00110-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,24]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["110"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00110-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2024,6,24]]},"assertion":[{"value":"24 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}