Clases de gráficos con ancho de árbol superconstante

10

Hay varias clases interesantes de gráficos con ancho de árbol acotado. Por ejemplo, árboles (ancho de árbol 1), gráficos paralelos en serie (ancho de árbol 2), gráficos de plano externo (ancho de árbol 2), gráficos -outerplanar (ancho de árbol O (k)), gráficos de ancho de rama k (ancho de árbol O (k)), .. .kk

Pregunta: ¿Hay ejemplos de clases interesantes de gráficos cuyo ancho de árbol no esté limitado por una constante, sino por una función de bajo crecimiento?

  1. ¿Existen clases de gráficos bien conocidas con el ancho de árbol ?O(Iniciar sesiónIniciar sesiónnorte)
  2. ¿Hay clases bien conocidas de gráficos con el ancho de árbol ?O(Iniciar sesiónnorte)

También estaría interesado en clases de gráficos con treewidth o O ( log log . . . N ) donde el logaritmo se repite un número constante de veces.O(Iniciar sesiónknorte)O(Iniciar sesiónIniciar sesión...norte)

Obs: Por supuesto, es fácil cocinar familias artificiales de gráficos con un ancho de árbol dado, como la familia deO(Iniciar sesiónnorte)×norterejillas Así que estoy buscando principalmente una familia de gráficos que se hayan estudiado en otras ramas de la teoría de gráficos y que tengan un ancho de árbol u O ( log log n ) , pero un ancho de árbol no constante.O(Iniciar sesiónnorte)O(Iniciar sesiónIniciar sesiónnorte)

Mateus de Oliveira Oliveira
fuente
3
Los gráficos libres menores (planar ++) tienen un ancho de árbol O((norte))O(Iniciar sesiónnorte)
norteO(Iniciar sesiónnorte)norte

Respuestas:

14

Θ(Iniciar sesiónnorte)

Θ(norte)

David Eppstein
fuente