Dureté typique de la décomposition des arbres?

La décomposition des arbres est difficile dans le pire des cas, mais la méthode gourmande semble être presque optimale sur les petits réseaux réels.

1. Sait-on quelque chose sur la dureté de la décomposition des arbres d'une instance "typique" d'une classe de graphes?
2. Existe-t-il un exemple de famille de graphiques où les méthodes gourmandes de décomposition des arbres fonctionnent mal?

Je viens de tomber sur un article pertinent - Kloks / Boedlander "Seuls quelques graphiques ont une largeur d'arbre limitée". Ils montrent que presque tous les graphes avec sommets et δ n bords ont une largeur d'arbre de l'ordre de n ϵ , ϵ = δ - $n$$\delta n$$n^\epsilon$$\epsilon=\frac{\delta-1}{\delta+1}$$\delta=3$$\sqrt{n}$

Donc, même si la méthode gourmande trouvait la meilleure décomposition pour tous les graphiques, l'algorithme résultant serait toujours incroyablement lent pour les graphiques typiques