zbMATH — the first resource for mathematics

Characterizing width two for variants of treewidth. (English) Zbl 1350.05116
Summary: In this paper, we consider the notion of special treewidth, recently introduced by B. Courcelle [ibid. 160, No. 6, 866–887 (2012; Zbl 1236.05143)]. In a special tree decomposition, for each vertex \(v\) in a given graph, the bags containing \(v\) form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion.
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each \(k \geq 3\), the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most \(k\), is not closed under taking minors.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
03B15 Higher-order logic; type theory (MSC2010)
Full Text: DOI
[1] Archdeacon, D., A Kuratowski theorem for the projective plane, J. Graph Theory, 7, 325-334, (1983)
[2] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 11-24, (1989) · Zbl 0666.68067
[3] Arnborg, S.; Proskurowski, A.; Corneil, D. G., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1-19, (1990) · Zbl 0701.05016
[4] Barát, J.; Hajnal, P.; Lin, Y.; Yang, A., On the structure of graphs with path-width at most two, Studia Sci. Math. Hungar., 49, 2, 211-222, (2012) · Zbl 1289.05443
[5] Bibelnieks, E.; Dearing, P. M., Neighborhood subtree tolerance graphs, Discrete Appl. Math., 43, 1, 13-26, (1993) · Zbl 0788.05083
[6] Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-2, 1-45, (1998) · Zbl 0912.68148
[7] Bodlaender, H. L.; de Fluiter, B., On intervalizing \(k\)-colored graphs for DNA physical mapping, Discrete Appl. Math., 71, 55-77, (1996) · Zbl 0867.92008
[8] Bodlaender, H. L.; Deogun, J. S.; Kansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Z., Rankings of graphs, SIAM J. Discrete Math., 11, 168-181, (1998) · Zbl 0907.68137
[9] Bodlaender, H. L.; Gilbert, J. R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and minimum elimination tree height, J. Algorithms, 18, 238-255, (1995) · Zbl 0818.68118
[10] Bodlaender, H. L.; Kloks, T., A simple linear time algorithm for triangulating three-colored graphs, J. Algorithms, 15, 160-172, (1993) · Zbl 0785.68042
[11] Bodlaender, H. L.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21, 358-402, (1996) · Zbl 0861.68036
[12] Bodlaender, H. L.; Kratsch, S.; Kreuzen, V. J.C., Fixed-parameter tractability and characterizations of small special treewidth, (Brandstädt, A.; Jansen, K.; Reischuk, R., Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lecture Notes in Computer Science, vol. 8165, (2013), Springer Verlag), 88-99 · Zbl 1400.05234
[13] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph classes: A survey, (SIAM Monographs on Discrete Mathematics and Applications, (1999), Society for Industrial and Applied Mathematics, SIAM Philadelphia, PA) · Zbl 0919.05001
[14] Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 12-75, (1990) · Zbl 0722.03008
[15] Courcelle, B., On the model-checking of monadic second-order formulas with edge set quantifications, Discrete Appl. Math., 160, 6, 866-887, (2012) · Zbl 1236.05143
[16] deFluiter, B., Algorithms for graphs of small treewidth, (1997), Utrecht University, (Ph.D. thesis)
[17] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2010), Springer Heidelberg) · Zbl 1204.05001
[18] Dvořák, Z.; Giannopoulou, A. C.; Thilikos, D. M., Forbidden graphs for tree-depth, European J. Combin., 33, 5, 969-979, (2012) · Zbl 1239.05062
[19] Ellis, J. A.; Sudborough, I. H.; Turner, J., The vertex separation and search number of a graph, Inform. and Comput., 113, 50-79, (1994) · Zbl 0942.68641
[20] Farber, M., Applications of linear programming duality to problems involving independence and domination, (1982), Rutgers University, (Ph.D. thesis)
[21] Farber, M., Characterizations of strongly chordal graphs, Discrete Math., 43, 2-3, 173-189, (1983) · Zbl 0514.05048
[22] Fomin, F. V.; Fraigniaud, P.; Nisse, N., Nondeterministic graph searching: from pathwidth to treewidth, Algorithmica, 53, 358-373, (2009) · Zbl 1172.68046
[23] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[24] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete Math., 23, 211-227, (1978) · Zbl 0398.05060
[25] Golumbic, M. C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[26] Golumbic, M. C.; Jamison, R. E., Edge and vertex intersections of paths in a tree, Discrete Math., 55, 151-159, (1985) · Zbl 0568.05023
[27] Kinnersley, N. G.; Langston, M. A., Obstruction set isolation for the gate matrix layout problem, Discrete Appl. Math., 54, 169-213, (1994) · Zbl 0941.68590
[28] Kloks, T., (Treewidth. Computations and Approximations, Lecture Notes in Computer Science, vol. 842, (1994), Springer Verlag Berlin) · Zbl 0825.68144
[29] Lagergren, J.; Arnborg, S., Finding minimal forbidden minors using a finite congruence, (Albert, J. L.; Monien, B.; Rodríguez-Artalejo, M., Proceedings of the 18th International Colloquium on Automata, Languages and Programming, ICALP’91, Lecture Notes in Computer Science, vol. 510, (1991), Springer Verlag), 532-543 · Zbl 0764.68122
[30] Monma, C. L.; Wei, V. K., Intersection graphs of paths in a tree, J. Combin. Theory Ser. B, 41, 141-181, (1986) · Zbl 0595.05062
[31] Panda, B. S., The forbidden subgraph characterization of directed vertex graphs, Discrete Math., 196, 1-3, 239-256, (1999) · Zbl 0928.05029
[32] Proskurowski, A., Maximal graphs of pathwidth \(k\) or searching a partial \(k\)-caterpillar, technical report CIS-TR-89-17, dept. of computer and information science, (1989), University of Oregon
[33] Robertson, N.; Seymour, P. D., Graph minors. XX. wagner’s conjecture, J. Combin. Theory Ser. B, 92, 325-357, (2004) · Zbl 1061.05088
[34] Robertson, N.; Seymour, P. D., Graph minors. I. excluding a forest, J. Combin. Theory Ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[35] Robertson, N.; Seymour, P. D., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[36] Satyanarayana, A.; Tung, L., A characterization of partial 3-trees, Networks, 20, 299-322, (1990) · Zbl 0701.90092
[37] Wagner, K., Über eine eigenshaft der ebenen complexe, Math. Ann., 14, 570-590, (1937) · JFM 63.0550.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.