{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:48:22Z","timestamp":1764557302482,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Greek national funds through the Operational Program \u201cEducation and Lifelong Learning\u201d"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["208471 - ExploreMaps project"],"award-info":[{"award-number":["208471 - ExploreMaps project"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on<jats:italic>n<\/jats:italic>vertices and branchwidth at most<jats:italic>k<\/jats:italic>. Our technique applies to general families of problems where standard dynamic programming runs in 2<jats:sup><jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>\u22c5log<jats:italic>k<\/jats:italic>)<\/jats:sup>\u22c5<jats:italic>n<\/jats:italic>steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called<jats:italic>surface cut decomposition<\/jats:italic>, generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth<jats:italic>k<\/jats:italic>) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2<jats:sup><jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>)<\/jats:sup>\u22c5<jats:italic>n<\/jats:italic>steps. That way, we considerably extend the class of problems that can be solved in running times with a<jats:italic>single-exponential dependence<\/jats:italic>on branchwidth and unify\/improve most previous results in this direction.<\/jats:p>","DOI":"10.1145\/2556952","type":"journal-article","created":{"date-parts":[[2014,2,7]],"date-time":"2014-02-07T14:22:52Z","timestamp":1391782972000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Dynamic programming for graphs on surfaces"],"prefix":"10.1145","volume":"10","author":[{"given":"Juanjo","family":"Ru\u00e9","sequence":"first","affiliation":[{"name":"ICM, Madrid, Spain"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[{"name":"CNRS-LIRMM, Montpellier, France"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2014,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_31"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2074022.2074024"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3765.3773"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_23"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646242.681417"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00074-6"},{"key":"e_1_2_1_8_1","volume-title":"14th International Workshop on Graph-theoretic Concepts in Computer Science (WG\u201988)","volume":"344","author":"Courcelle Bruno","year":"1988","unstructured":"Bruno Courcelle . 1988 . The monadic second-order logic of graphs: definable sets of finite graphs . In 14th International Workshop on Graph-theoretic Concepts in Computer Science (WG\u201988) . LNCS, Vol. 344 . 30--53. Bruno Courcelle. 1988. The monadic second-order logic of graphs: definable sets of finite graphs. In 14th International Workshop on Graph-theoretic Concepts in Computer Science (WG\u201988). LNCS, Vol. 344. 30--53."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/040616929"},{"key":"e_1_2_1_12_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2005. Graph Theory ( 3 rd ed.). Graduate Texts in Mathematics, Vol. 173 . Springer Verlag . Reinhard Diestel. 2005. Graph Theory (3rd ed.). Graduate Texts in Mathematics, Vol. 173. Springer Verlag.","edition":"3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_18"},{"key":"e_1_2_1_14_1","first-page":"15","article-title":"Subexponential parameterized algorithms. In 34th International Colloquium on Automata, Languages and Programming (ICALP\u201907)","volume":"4596","author":"Dorn Frederic","year":"2007","unstructured":"Frederic Dorn , Fedor V. Fomin , and Dimitrios M. Thilikos . 2007 . Subexponential parameterized algorithms. In 34th International Colloquium on Automata, Languages and Programming (ICALP\u201907) . LNCS , Vol. 4596. 15 -- 27 . Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. 2007. Subexponential parameterized algorithms. In 34th International Colloquium on Automata, Languages and Programming (ICALP\u201907). LNCS, Vol. 4596. 15--27.","journal-title":"LNCS"},{"volume-title":"19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Dorn Frederic","key":"e_1_2_1_15_1","unstructured":"Frederic Dorn , Fedor V. Fomin , and Dimitrios M. Thilikos . 2008. Catalan structures and dynamic programming in H-minor-free graphs . In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . Philadelphia, PA, 631--640. Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. 2008. Catalan structures and dynamic programming in H-minor-free graphs. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). Philadelphia, PA, 631--640."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer-Verlag New York. R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_18_1","volume-title":"14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Eppstein David","year":"2003","unstructured":"David Eppstein . 2003 . Dynamic generators of topologically embedded graphs . In 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903) . 599--608. David Eppstein. 2003. Dynamic generators of topologically embedded graphs. In 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 599--608."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"P. Flajolet and R. Sedgewick. 2008. Analytic Combinatorics. Cambridge Univ. Press. P. Flajolet and R. Sedgewick. 2008. Analytic Combinatorics. Cambridge Univ. Press.","DOI":"10.1017\/CBO9780511801655"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_20_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_50"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419649"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v55:1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1055"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133096"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"B. Mohar and C. Thomassen. 2001. Graphs on surfaces. John Hopkins University Press. B. Mohar and C. Thomassen. 2001. Graphs on surfaces. John Hopkins University Press.","DOI":"10.56021\/9780801866890"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier Rolf","key":"e_1_2_1_32_1","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications , Vol. 31 . Oxford University Press , Oxford . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1034"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1919"},{"key":"e_1_2_1_36_1","volume-title":"Thilikos","author":"Ru\u00e9 Juanjo","year":"2011","unstructured":"Juanjo Ru\u00e9 , Ignasi Sau , and Dimitrios M . Thilikos . 2011 . Asymptotic enumeration of non-crossing partitions on surfaces. Manuscript submitted for publication, available at http:\/\/lanl.arxiv.org\/abs\/1104.2477. Juanjo Ru\u00e9, Ignasi Sau, and Dimitrios M. Thilikos. 2011. Asymptotic enumeration of non-crossing partitions on surfaces. Manuscript submitted for publication, available at http:\/\/lanl.arxiv.org\/abs\/1104.2477."},{"key":"e_1_2_1_37_1","volume-title":"Thilikos","author":"Ru\u00e9 Juanjo","year":"2012","unstructured":"Juanjo Ru\u00e9 , Ignasi Sau , and Dimitrios M . Thilikos . 2012 . Dynamic programming for minor-free graphs. (2012). Manuscript in preparation. Juanjo Ru\u00e9, Ignasi Sau, and Dimitrios M. Thilikos. 2012. Dynamic programming for minor-free graphs. (2012). Manuscript in preparation."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.02.002"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556952","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2556952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:41Z","timestamp":1750232081000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2556952"],"URL":"https:\/\/doi.org\/10.1145\/2556952","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2011-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}