Wyrażenia o szerokości kliki z głębokością logarytmiczną

Kiedy otrzymujemy rozkład drzewa wykresu o szerokości , istnieje kilka sposobów, dzięki którym możemy go uczynić „ładnym”. W szczególności wiadomo, że można go przekształcić w rozkład drzewa, w którym drzewo jest binarne, a jego wysokość wynosi . Można to osiągnąć przy zachowaniu szerokości rozkładu co najwyżej . (Patrz np. „Algorytmy równoległe z optymalnym przyspieszeniem dla ograniczonej szerokości drogi”, autorstwa Bodlaender i Hagerup). Głębokość logarytmiczna jest więc właściwością rozkładu drzewa, którą możemy uzyskać prawie za darmo.$G$$w$$O(\log n)$$3w$

Moje pytanie brzmi, czy istnieje podobny wynik dla szerokości kliki, czy może kontrprzykład. Innymi słowy, biorąc pod uwagę wyrażenie szerokości kliki dla przy użyciu etykiet, czy zawsze istnieje wyrażenie szerokości kliki o wysokości dla , które używa co najwyżej etykiet? Tutaj wysokość jest definiowana naturalnie jako wysokość drzewa parsowania wyrażenia szerokości kliki.$G$$k$$O(\log n)$$G$$f(k)$

Jeśli stwierdzenie podobne do powyższego nie jest znane, czy istnieje przykład wykresu odwróconego z małą szerokością kliki , tak że jedynym sposobem konstruowania pomocą etykiet jest użycie wyrażenia głębokość?$n$$G$$k$$G$$f(k)$

Po chwili znalazłem odpowiedź w literaturze, więc zamieszczam ją tutaj, na wypadek, gdyby była przydatna dla kogoś innego.

W rzeczywistości możliwe jest ponowne zrównoważenie wyrażeń szerokości kliki, aby miały one głębokość logarytmiczną. Wynik podano w artykule „Operacje na wykresach charakteryzujące szerokość rang i wyrażenia wykresów zrównoważonych” autorstwa Courcelle i Kanté, WG '08. Cytuję Twierdzenie 4.4 z pracy:

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

Problem polega na tym, że liczba etykiet wysadza się wykładniczo w równoważeniu. Wydaje się, że dla szerokości kliki nie jest obecnie znany lepszy wynik. Ten sam papier daje podobny wynik z ciągłym powiększaniem szerokości rangi, ale to nie pomaga, ponieważ różnica między szerokością kliki a szerokością rangi może być wykładnicza w najgorszym przypadku.