Expresiones de ancho de camarilla con profundidad logarítmica

Cuando se nos da una descomposición de árbol de un gráfico con ancho w , hay varias formas en que podemos hacer que sea "agradable". En particular, se sabe que es posible transformarlo en una descomposición del árbol donde el árbol es binario y su altura es O ( log n ) . Esto se puede lograr manteniendo el ancho de la descomposición como máximo 3 w . (Ver, por ejemplo, "Algoritmos paralelos con velocidad óptima para el ancho del árbol acotado", por Bodlaender y Hagerup). Entonces, la profundidad logarítmica es una propiedad de la descomposición de un árbol que podemos obtener casi gratis.$G$$w$$O(\log n)$$3w$

Mi pregunta es si existe un resultado similar para el ancho de la camarilla, o tal vez un contraejemplo. En otras palabras, dada una expresión de ancho de camarilla para usando k etiquetas, ¿siempre existe una expresión de ancho de camarilla de altura O ( log n ) para G , que usa como máximo f ( k ) etiquetas? Aquí, la altura se define naturalmente como la altura del árbol de análisis de la expresión de ancho de camarilla.$G$$k$$O(\log n)$$G$$f(k)$

Si no se conoce un enunciado similar al anterior, ¿hay un ejemplo de un gráfico vértices G con un ancho de camarilla pequeño k , de modo que la única forma de construir G con etiquetas f ( k ) sea ​​usar una expresión con gran ¿profundidad?$n$$G$$k$$G$$f(k)$

Después de un tiempo encontré una respuesta en la literatura, así que la publico aquí en caso de que sea útil para otra persona.

De hecho, es posible reequilibrar expresiones de ancho de camarilla para que tengan profundidad logarítmica. El resultado se da en el documento "Operaciones gráficas que caracterizan el ancho de rango y las expresiones gráficas balanceadas" de Courcelle y Kanté, WG '08. Cito el teorema 4.4 del artículo:

$k$$k \times 2^{k+1}$

El problema aquí es que el número de etiquetas explota exponencialmente en el equilibrio. Parece que para el ancho de la camarilla no se conoce actualmente ningún resultado mejor. El mismo documento da un resultado similar con solo una ampliación constante del ancho de rango, pero esto no ayuda, ya que la diferencia entre el ancho de la camarilla y el ancho de rango puede ser exponencial en el peor de los casos.