Expressions de largeur de clique avec profondeur logarithmique

Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en gardant la largeur de la décomposition au maximum 3w . (Voir par exemple "Algorithmes parallèles avec une accélération optimale pour une largeur d'arbre limitée", par Bodlaender et Hagerup). Ainsi, la profondeur logarithmique est une propriété d'une décomposition d'arbre que nous pouvons obtenir presque gratuitement.$G$$w$$O(\log n)$$3w$

Ma question est de savoir s'il existe un résultat similaire pour la largeur de clique, ou peut-être un contre-exemple. En d'autres termes, étant donné une expression de largeur de clique pour $G$ utilisant $k$ étiquettes, existe-t-il toujours une expression de largeur de clique de hauteur $O(\log n)$ pour $G$ , qui utilise au plus $f(k)$ étiquettes? Ici, la hauteur est définie naturellement comme la hauteur de l'arbre d'analyse de l'expression de largeur de clique.

Si une instruction similaire à la précédente n'est pas connue, existe-t-il un exemple de graphe $n$ sommet $G$ avec une petite largeur de clique $k$ , de sorte que la seule façon de construire $G$ avec des étiquettes $f(k)$ est d'utiliser une expression avec un grand profondeur?

Après un certain temps, j'ai trouvé une réponse dans la littérature, donc je la poste ici au cas où elle serait utile à quelqu'un d'autre.

Il est en effet possible de rééquilibrer les expressions de largeur de clique afin qu'elles aient une profondeur logarithmique. Le résultat est donné dans l'article "Opérations graphiques caractérisant la largeur de rang et les expressions graphiques équilibrées" par Courcelle et Kanté, WG '08. Je cite le théorème 4.4 du document:

"Chaque graphique de largeur de clique ou de largeur NLC est la valeur d'une expression de largeur de clique équilibrée à 3 de largeur de clique ou de largeur NLC au plus "$k$$k \times 2^{k+1}$

Le hic ici est que le nombre d'étiquettes explose de façon exponentielle dans l'équilibrage. Il semble que pour la largeur de clique, aucun meilleur résultat ne soit actuellement connu. Le même article donne un résultat similaire avec seulement une explosion constante pour la largeur de rang, mais cela n'aide pas, car la différence entre largeur de clique et largeur de rang peut être exponentielle dans le pire des cas.