Ainda está aberto para determinar a complexidade da computação da largura de árvore dos gráficos planares?

Para uma constante , pode-se determinar em tempo linear, dado um gráfico de entrada , se sua largura de árvore é . No entanto, quando e são dados como entrada, o problema é NP-difícil. ( Fonte ). G ≤ k k $k \in \mathbb{N}$$G$$\leq k$$k$$G$

No entanto, quando o gráfico de entrada é plano , muito menos parece ser conhecido sobre a complexidade. Aparentemente, o problema foi aberto em 2010, uma reivindicação que também apareceu nesta pesquisa em 2007 e na página da Wikipedia para decomposições de ramos . Por outro lado, o problema é reivindicado NP-hard (sem prova de referência) em uma versão anterior da pesquisa mencionada anteriormente, mas presumo que seja um erro.

Ainda está aberto para determinar a complexidade do problema, dado e um gráfico planar , de determinação de com largura da árvore ? Se for, isso foi reivindicado em um artigo recente? Existem resultados parciais conhecidos? Se não for, quem resolveu? G G ≤ $k \in \mathbb{N}$$G$$G$$\leq k$

Até onde eu sei, a completude NP da computação ainda está aberta. A referência mais recente que conheço é uma pesquisa realizada pela Bodlaender em 2012, chamada `` Rastreabilidade de parâmetros fixos da largura de árvore e largura de caminho '', que apareceu no festschrift no 65º aniversário de Mike Fellows. O problema está listado na conclusão da pesquisa.