{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:42Z","timestamp":1781078262880,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["617951 and 853234"],"award-info":[{"award-number":["617951 and 853234"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384261","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1293-1306","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Detecting and counting small patterns in planar graphs in subexponential parameterized time"],"prefix":"10.1145","author":[{"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[{"name":"Utrecht University, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"issue":"4","key":"e_1_3_2_1_1_1","first-page":"844","volume":"42","author":"Alon Noga","year":"1995","unstructured":"Noga Alon , Raphael Yuster , and Uri Zwick . Color-coding. J. ACM , 42 ( 4 ): 844 \u2013 856 , 1995 . Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844\u2013856, 1995.","journal-title":"Color-coding. J. ACM"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"issue":"275","key":"e_1_3_2_1_3_1","first-page":"279","article-title":"On triangulating k-outerplanar graphs","volume":"181","author":"Biedl Therese","year":"2015","unstructured":"Therese Biedl . On triangulating k-outerplanar graphs . Discrete Applied Mathematics , 181 : 275 \u2013 279 , 2015 . Therese Biedl. On triangulating k-outerplanar graphs. Discrete Applied Mathematics, 181:275 \u2013 279, 2015.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_1_4_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Bodlaender Hans L.","year":"2016","unstructured":"Hans L. Bodlaender , Jesper Nederlof , and Tom C . van der Zanden. Subexponential time algorithms for embedding H-minor free graphs. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016 , Rome, Italy, pages 9:1\u20139:14 , 2016. Hans L. Bodlaender, Jesper Nederlof, and Tom C. van der Zanden. Subexponential time algorithms for embedding H-minor free graphs. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 9:1\u20139:14, 2016."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"issue":"1","key":"e_1_3_2_1_7_1","first-page":"103","article-title":"Randomization in Parameterized Complexity (Dagstuhl Seminar 17041)","volume":"7","author":"Cygan Marek","year":"2017","unstructured":"Marek Cygan , Fedor V. Fomin , Danny Hermelin , and Magnus Wahlstr\u00f6m . Randomization in Parameterized Complexity (Dagstuhl Seminar 17041) . Dagstuhl Reports , 7 ( 1 ): 103 \u2013 128 , 2017 . Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlstr\u00f6m. Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). Dagstuhl Reports, 7(1):103\u2013128, 2017.","journal-title":"Dagstuhl Reports"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_2_1_9_1","first-page":"94","volume-title":"Single-source stochastic routing","author":"Chawla Shuchi","year":"2006","unstructured":"Shuchi Chawla and Tim Roughgarden . Single-source stochastic routing . In Josep D\u00edaz, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization , and Combinatorial Optimization. Algorithms and Techniques, pages 82\u2013 94 , Berlin, Heidelberg, 2006 . Springer Berlin Heidelberg . Shuchi Chawla and Tim Roughgarden. Single-source stochastic routing. In Josep D\u00edaz, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 82\u201394, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg."},{"key":"e_1_3_2_1_10_1","first-page":"17","volume-title":"24th Annual European Symposium on Algorithms, ESA 2016","volume":"57","author":"Curticapean Radu","year":"2016","unstructured":"Radu Curticapean . Counting matchings with k unmatched vertices in planar graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors , 24th Annual European Symposium on Algorithms, ESA 2016 , August 22-24, 2016 , Aarhus, Denmark , volume 57 of LIPIcs, pages 33:1\u201333: 17 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Radu Curticapean. Counting matchings with k unmatched vertices in planar graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 33:1\u201333:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016."},{"key":"e_1_3_2_1_11_1","first-page":"18","volume-title":"13th International Symposium on Parameterized and Exact Computation, IPEC 2018","volume":"115","author":"Curticapean Radu","year":"2018","unstructured":"Radu Curticapean . Counting problems in parameterized complexity. In Christophe Paul and Michal Pilipczuk, editors , 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 , August 20-24, 2018 , Helsinki, Finland , volume 115 of LIPIcs, pages 1:1\u20131: 18 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Radu Curticapean. Counting problems in parameterized complexity. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, volume 115 of LIPIcs, pages 1:1\u20131:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528993X"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.11.006"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.16"},{"key":"e_1_3_2_1_16_1","volume-title":"33rd International Workshop, WG 2007","volume":"4769","author":"Dorn Frederic","year":"2007","unstructured":"Frederic Dorn . How to use planarity efficiently: New tree-decomposition based algorithms. In Andreas Brandst\u00e4dt, Dieter Kratsch, and Haiko M\u00fcller, editors, Graph-Theoretic Concepts in Computer Science , 33rd International Workshop, WG 2007 , Dornburg, Germany , June 21-23, 2007 . Revised Papers, volume 4769 of Lecture Notes in Computer Science, pages 280\u2013291. Springer, 2007. Frederic Dorn. How to use planarity efficiently: New tree-decomposition based algorithms. In Andreas Brandst\u00e4dt, Dieter Kratsch, and Haiko M\u00fcller, editors, Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769 of Lecture Notes in Computer Science, pages 280\u2013291. Springer, 2007."},{"key":"e_1_3_2_1_17_1","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","author":"Dorn Frederic","year":"2010","unstructured":"Frederic Dorn . Planar subgraph isomorphism revisited . In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 , March 4-6, 2010 , Nancy, France, pages 263\u2013274 , 2010. Frederic Dorn. Planar subgraph isomorphism revisited. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 263\u2013274, 2010."},{"key":"e_1_3_2_1_18_1","unstructured":"David Eppstein Georg Gottlob and Jan Arne Telle. Nerode prize 2015: Winner announcement. Available at http:\/\/eatcs.org\/images\/awards\/Nerode15-laudation.pdf.  David Eppstein Georg Gottlob and Jan Arne Telle. Nerode prize 2015: Winner announcement. Available at http:\/\/eatcs.org\/images\/awards\/Nerode15-laudation.pdf."},{"issue":"5","key":"e_1_3_2_1_19_1","first-page":"94","article-title":"Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)","volume":"6","author":"Erickson Jeff","year":"2016","unstructured":"Jeff Erickson , Philip N. Klein , D\u00e1niel Marx , and Claire Mathieu . Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221) . Dagstuhl Reports , 6 ( 5 ): 94 \u2013 116 , 2016 . Jeff Erickson, Philip N. Klein, D\u00e1niel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports, 6(5):94\u2013116, 2016.","journal-title":"Dagstuhl Reports"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1111-9"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.06.007"},{"issue":"1","key":"e_1_3_2_1_24_1","first-page":"13","article-title":"Tree-width and large grid minors in planar graphs","volume":"13","author":"Grigoriev Alexander","year":"2011","unstructured":"Alexander Grigoriev . Tree-width and large grid minors in planar graphs . Discrete Mathematics & Theoretical Computer Science , 13 ( 1 ): 13 \u2013 20 , 2011 . Alexander Grigoriev. Tree-width and large grid minors in planar graphs. Discrete Mathematics & Theoretical Computer Science, 13(1):13\u201320, 2011.","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"e_1_3_2_1_25_1","first-page":"184","volume-title":"Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC \u201974","author":"John","year":"1974","unstructured":"John E. Hopcroft and Jin K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report) . In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC \u201974 , pages 172\u2013 184 , New York, NY, USA , 1974 . ACM. John E. Hopcroft and Jin K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC \u201974, pages 172\u2013184, New York, NY, USA, 1974. ACM."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"e_1_3_2_1_27_1","unstructured":"Philip Klein and Shay Mozes. Planarity (book draft). http:\/\/planarity.org\/.  Philip Klein and Shay Mozes. Planarity (book draft). http:\/\/planarity.org\/."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_41"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"e_1_3_2_1_32_1","volume-title":"Detecting and counting small patterns in planar graphs in subexponential parameterized time. CoRR, abs\/1904.11285","author":"Nederlof Jesper","year":"2019","unstructured":"Jesper Nederlof . Detecting and counting small patterns in planar graphs in subexponential parameterized time. CoRR, abs\/1904.11285 , 2019 . Jesper Nederlof. Detecting and counting small patterns in planar graphs in subexponential parameterized time. CoRR, abs\/1904.11285, 2019."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0511-9"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_1_36_1","volume-title":"Problems of unknown complexity : graph isomorphism and ramsey theoretic numbers. 09","author":"Schweitzer Pascal","year":"2009","unstructured":"Pascal Schweitzer . Problems of unknown complexity : graph isomorphism and ramsey theoretic numbers. 09 2009 . Pascal Schweitzer. Problems of unknown complexity : graph isomorphism and ramsey theoretic numbers. 09 2009."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.014"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.4"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384261","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":38,"alternative-id":["10.1145\/3357713.3384261","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384261","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}