Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth

Arnborg, 1991, Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308, 10.1016/0196-6774(91)90006-K Arnborg, 1986, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305, 10.1137/0607033 Arnborg, 1989, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math., 23, 11, 10.1016/0166-218X(89)90031-0 Baker, 1994, Approximation algorithms for NP-complete problems on planar graphs, J. Assoc. Comput. Mach., 41, 153, 10.1145/174644.174650 Bern, 1987, Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216, 10.1016/0196-6774(87)90039-3 Bodlaender, 1996, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305, 10.1137/S0097539793251219 Hans L. Bodlaender, Treewidth: Algorithmic techniques and results, in: Proc. 22nd Internat. Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29–36 Bodlaender, 1998, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1, 10.1016/S0304-3975(97)00228-4 Bondy, 1976 Franz J. Brandenburg, Pattern matching problems in graphs, manuscript, 2001 Demaine, 2002, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, J. Comput. System Sci., 42, 69 Dessmark, 2000, Faster algorithms for subgraph isomorphism of k-connected partial k-trees, Algorithmica, 27, 337, 10.1007/s004530010023 Dessmark, 2000, Maximum packing for k-connected partial k-trees in polynomial time, Theoret. Comput. Sci., 236, 179, 10.1016/S0304-3975(99)00208-X Eppstein, 1999, Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl., 3, 10.7155/jgaa.00014 Eppstein, 2000, Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 275, 10.1007/s004530010020 Frick, 2001, Deciding first-order properties of locally tree-decomposable structures, J. Assoc. Comput. Mach., 48, 1184, 10.1145/504794.504798 Garey, 1979 Garey, 1976, The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704, 10.1137/0205049 Grohe, 2003, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23, 613, 10.1007/s00493-003-0037-9 Gupta, 1996, The complexity of subgraph isomorphism for classes of partial k-trees, Theoret. Comput. Sci., 164, 287, 10.1016/0304-3975(96)00046-1 Arvind Gupta, Naomi Nishimura, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, in: Proc. 4th Scandinavian Workshop on Algorithm Theory, 1994, pp. 172–182 Hajiaghayi Hajiaghayi, 2003, A note on the bounded fragmentation property and its applications in network reliability, European J. Combin., 24, 891, 10.1016/S0195-6698(03)00080-5 van Leeuwen, 1990, Graph algorithms, vol. A, 525 Lingas, 1989, Subgraph isomorphism for biconnected outerplanar graphs in cubic time, Theoret. Comput. Sci., 63, 295, 10.1016/0304-3975(89)90011-X Lingas, 1988, A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs, 394 Matoušek, 1992, On the complexity of finding iso- and other morphisms for partial k-trees, Discrete Math., 108, 343, 10.1016/0012-365X(92)90687-B Matula, 1978, Subtree isomorphism in O(n5/2), vol. 2, 91 Robertson, 1986, Graph minors II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Sanders, 1996, On linear recognition of tree-width at most four, SIAM J. Discrete Math., 9, 101, 10.1137/S0895480193243043 Sysło, 1982, The subgraph isomorphism problem for outerplanar graphs, Theoret. Comput. Sci., 17, 91, 10.1016/0304-3975(82)90133-5