¿Todavía está abierto para determinar la complejidad de calcular el ancho de árbol de los gráficos planos?

Para una constante , se puede determinar en tiempo lineal, dado un gráfico de entrada G , si su ancho de árbol es ≤ k . Sin embargo, cuando k y G se dan como entrada, el problema es NP-hard. ( Fuente )$k \in \mathbb{N}$$G$$\leq k$$k$$G$

Sin embargo, cuando el gráfico de entrada es plano , parece que se sabe mucho menos sobre la complejidad. El problema aparentemente se abrió en 2010, una afirmación que también apareció en esta encuesta en 2007 y en la página de Wikipedia para descomposiciones de sucursales . Por el contrario, el problema se afirma NP-hard (sin prueba de referencia) en una versión anterior de la encuesta mencionada anteriormente, pero supongo que esto es un error.

¿Todavía está abierto para determinar la complejidad del problema, dado y un gráfico plano G , de determinar que G tiene un ancho de árbol ≤ k ? Si es así, ¿se afirmó esto en un artículo reciente? ¿Se conocen resultados parciales? Si no es así, ¿quién lo resolvió?$k \in \mathbb{N}$$G$$G$$\leq k$

Hasta donde yo sé, la integridad de NP de calcular el ancho de árbol de un gráfico plano todavía está abierta. La referencia más reciente que conozco es una encuesta realizada por Bodlaender de 2012 llamada `Trazabilidad de parámetros fijos de ancho de árbol y ancho de camino 'que apareció en el festschrift para el 65 cumpleaños de Mike Fellows. El problema aparece en la conclusión de la encuesta.