Computing treewidth of arbitrary graphs is NP-complete (Arnborg, Corneil, and Proskurowski 1987), but the graphs derived from SCFG permutations have a restricted structure that it might be possible to exploit.
the graphs have degree no greater than six.