Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

Amini, 2008, Degree-constrained subgraph problems: Hardness and approximation, vol. 5426, 29 Catlin, 1992, Supereulerian graphs: a survey, Journal of Graph Theory, 16, 177, 10.1002/jgt.3190160209 Demaine, 2005, Subexponential parameterized algorithms on graphs of bounded genus and h-minor-free graphs, Journal of the ACM, 52, 866, 10.1145/1101821.1101823 Dorn, 2007, Subexponential parameterized algorithms, vol. 4596, 15 F. Dorn, F.V. Fomin, D.M. Thilikos, Catalan structures and dynamic programming in H-minor-free graphs, in: Proc. of the 19th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 2008, pp. 631–640 Dorn, 2005, Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, vol. 3669, 95 Dorn, 2009, Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm, Discrete Applied Mathematics, 157, 2737, 10.1016/j.dam.2008.08.023 Flajolet, 2008 Flum, 2006 Fomin, 2005, New upper bounds on the decomposability of planar graphs, Journal of Graph Theory, 51, 53, 10.1002/jgt.20121 Fomin, 2006, Dominating sets in planar graphs: Branch-width and exponential speed-up, SIAM Journal on Computing, 36, 281, 10.1137/S0097539702419649 M. Fürer, B. Raghavachari, Approximating the minimum-degree spanning tree to within one from the optimal degree, in: Proc. of the 3rd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 1992, pp. 317–324 Garey, 1979 Gu, 2008, Optimal branch-decomposition of planar graphs in O(n3) time, ACM Transactions on Algorithms, 4, 10.1145/1367064.1367070 Gu, 2009, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n1+ε) time, vol. 5878, 984 Kreweras, 1972, Sur les partitions non croisées d'un cercle, Discrete Mathematics, 1, 333, 10.1016/0012-365X(72)90041-6 Lovász, 1986, Matching Theory, vol. 29 Robertson, 1991, Graph minors. X. Obstructions to tree-decomposition, J. Comb. Theory, Ser. B, 52, 153, 10.1016/0095-8956(91)90061-N Robertson, 1994, Quickly excluding a planar graph, J. Comb. Theory, Ser. B, 62, 323, 10.1006/jctb.1994.1073 Seymour, 1994, Call routing and the ratcatcher, Combinatorica, 14, 217, 10.1007/BF01215352