Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?

Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym).

Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP.

Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ?

Podobnie:

Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest łatwe? Jeśli tak, czy jest jakaś właściwość / test strukturalny, który można wykorzystać? Czyli wykres ma własność X ⇒ obliczeniowe treewidth z G ∈ P .$G$$X$ $\Rightarrow$$G \in \mathbf{P}$

$9$$2$$2$

$\Pi(G)$$G$$G$$O(|\Pi(G)|^2 \cdot n^{O(1)})$$G$$k$$2^{O(k^3)}n$$O((\log n)^{1/3})$

Niezwykle otwartym problemem jest to, czy obliczenie szerokości wykresów płaskich jest rozwiązaniem wielomianowym rozwiązanym czasowo, czy NP całkowitym. Warto zauważyć, że powiązana szerokość gałęzi parametru wykresu (która zawsze mieści się w współczynniku 1,5 od odległości od linii prostej) jest czasem wielomianowym obliczalnym na wykresach płaskich.