Treewidth of Cartesian Products of Highly Connected Graphs
David R. Wood · Journal of Graph Theory · 2012
Abstract The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.