×

Treewidth and logical definability of graph products. (English) Zbl 1162.68023

Summary: We describe an algorithm that, given a tree-decomposition of a graph \(G\) and a tree-decomposition of a graph \(H\), provides a tree-decomposition of the cartesian product of \(G\) and \(H\). Using this algorithm, we derive upper bounds on the treewidth (resp. on the pathwidth) of the cartesian product of two graphs, expressed in terms of the treewidth (resp. pathwidth) and the size of the factor graphs. In the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and that the cartesian product by a finite set of connected graphs preserves \(MS_{1}\)-definability and \(MS_{2}\)-definability. We also prove that the cartesian product of two \(MS_{2}\)-definable classes of connected graphs is \(MS_{2}\)-definable.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. System Theory, 20, 83-127 (1987) · Zbl 0641.68115
[2] Bodlaender, H. L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[3] Chlebíková, J., On the treewidth of a graph, Acta Math. Univ. Comenianae, 16, 2, 225-236 (1992) · Zbl 0821.05014
[4] B. Courcelle, Graph algebras and monadic second-order logic, Cambridge University Press, (in preparation). http://www.labri.fr/perso/courcell/ActSci.html; B. Courcelle, Graph algebras and monadic second-order logic, Cambridge University Press, (in preparation). http://www.labri.fr/perso/courcell/ActSci.html · Zbl 1143.68433
[5] Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, 85, 12-75 (1990), Presented at the International Workshop on Graph Grammars and their application to computer science, Warrenton, Virginia, 1986. LNCS Comp. Sci. vol. 291, pp. 133-146 · Zbl 0722.03008
[6] Courcelle, B., The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues, Theoretical Informatics and Applications, 26, 3, 257-286 (1992) · Zbl 0754.03006
[7] Courcelle, B., Graph grammars, monadic second-order logic and the theory of graph minors, (Graph Structure Theory. Graph Structure Theory, Contemporary Mathematics, vol. 147 (1993), American Mathematical Society), 565-590 · Zbl 0787.05086
[8] Courcelle, B., Tutorial, Basic notions of universal algebra for language theory and graph grammars, Theoret. Comput. Sci., 163, 1-54 (1996) · Zbl 0874.68170
[9] Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformation: vol. 1: Foundations (1997), World Scientific Publishing Co., Inc.), 313-400
[10] Downey, R. G.; Fellows, M. R., Parameterized complexity (1997), Springer · Zbl 0914.68076
[11] Imrich, W.; Klavzˆar, S., Product graphs: Structure and Recognition (2000), John Wiley and Sons, Inc.
[12] Möhring, R. H., Triangulating graphs without asteroidal triples, Discrete Appl. Math., 64, 281-287 (1996) · Zbl 0856.68112
[13] Seese, D., The structure of the models of decidable monadic theories of graphs, Ann. Pure Appl. Logic, 53, 169-195 (1991) · Zbl 0733.03026
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.