¿Los gráficos del "género delimitado por el exterior" tienen un ancho de árbol constante?

Deje y denote por G k el conjunto de todos los gráficos que se pueden incrustar en una superficie del género k de modo que todos los vértices estén situados en la cara externa . Por ejemplo, G 0 es el conjunto de gráficos de plano exterior. ¿Puede el ancho de árbol de los gráficos en G k estar limitado por alguna función de k ?$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

La otra dirección obviamente no se cumple, ya que el ancho de árbol constante ni siquiera implica un género constante: Sea la unión de n copias disjuntas de K 3 , 3 . El ancho de árbol de H n es constante, sin embargo, su género es n .$H_n$$n$$K_{3,3}$$H_n$$n$

Si.

Agregue un vértice en el medio de la cara externa, conectado a todos los vértices en la cara externa; Esto no cambia el género y no disminuye el ancho del árbol. Ahora el gráfico tiene un árbol de búsqueda de primer orden de amplitud muy poco profundo enraizado en el nuevo vértice (todo está adyacente a él).

Forme un árbol de expansión del gráfico dual cuyos bordes duales son disjuntos de los bordes del primer árbol de búsqueda de ancho. Luego hay un conjunto de bordes O (género) que no pertenecen a ninguno de los árboles. Cada uno de estos bordes induce un ciclo corto (un triángulo) junto con una ruta en el primer árbol de búsqueda de ancho, y cortar la superficie a lo largo de estos ciclos produce una superficie plana (ver mi artículo "Generadores dinámicos de gráficos integrados topológicamente"). Es decir, si G 'es el subgrafo del gráfico de entrada inducido por los vértices que no son puntos finales de los bordes de corte O (género), entonces G' es plano, y sus vértices pueden estar cubiertos por las caras O (género) de sus incrustación plana (las caras en las que los ciclos de corte cortan la cara externa original).

Pero en un gráfico plano en el que todos los vértices pertenecen a k caras, se pueden eliminar otros bordes O (k) (un árbol de expansión de las caras) para obtener un gráfico plano exterior. Entonces el ancho de árbol de G 'es O (género). Si uno forma una descomposición de árbol de G 'con este ancho, y luego agrega a cada bolsa los vértices que son los puntos finales de los bordes del ciclo de corte, el resultado es una descomposición de árbol del gráfico de entrada original con ancho de árbol O (género).

Parece probable que esto deba estar en la literatura ya en alguna parte, pero no sé dónde y algunas búsquedas rápidas no han logrado encontrar una declaración explícita de este resultado preciso. Sin embargo, una declaración más general se encuentra en otro artículo mío: en "Diámetro y ancho de árbol en familias de gráficos cerrados menores", pruebo, entre otras cosas, que los gráficos de género acotado del diámetro acotado tienen ancho de árbol acotado. En este caso (al agregar ese vértice adicional dentro de la cara externa), se puede tomar el diámetro como máximo dos.