Classes de gráficos com largura de árvore superconstante

Existem várias classes interessantes de gráficos com largura de árvore limitada. Por exemplo, árvores (largura da árvore 1), gráficos paralelos em série (largura da árvore 2), gráficos externos (largura da árvore 2), gráficos uterplanares (largura da árvore O (k)), gráficos da largura da ramificação (largura da árvore O (k)), .. . $k$ $k$

Pergunta: Existem exemplos de classes interessantes de gráficos cuja largura de árvore não é limitada por uma constante, mas por uma função de baixo crescimento?

Existem classes gráficas bem conhecidas com a largura da árvore ? $O(\log\log n)$
Existem classes gráficas bem conhecidas com a largura da árvore ? $O(\log n)$

Eu também estaria interessado em classes de gráficos com largura de árvore ou onde o logaritmo é repetido um número constante de vezes. $O(\log^k n)$ $O(\log\log...n)$

Obs: Obviamente, é fácil criar famílias artificiais de gráficos com uma determinada largura de árvore, como a família degrades. Então, estou procurando principalmente a família de gráficos que foram estudados em outros ramos da teoria dos grafos e que possuem largura de árvore ou , mas não constante. $\;O(\log n)\times n\;$ $O(\log n)$ $O(\log\log n)$

graph-theory treewidth Mateus de Oliveira Oliveira
fonte

Gráficos livres menores (++ planares) têm largura de árvore

, uma grande quantidade de classes de gráfico têm booleanwidth

, ver este papel:ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf

O (\sqrt{(} n))

$O(\sqrt(n))$

O (\log n)

$O(\log n)$

Daniello

@daniello Muito obrigado pelo seu comentário.

ainda é muito grande. Estou realmente interessado na largura da árvore, no máximo, polilogarítmica. O artigo sobre largura booleana é muito interessante e fornece várias classes interessantes com largura booleana

. Porém, como a largura booleana tem uma largura máxima de cliques ao quadrado, existem gráficos de largura booleana constante e

\sqrt{n}

$\sqrt{n}$

O (\log n)

$O(\log n)$

largura da árvore. Portanto, os resultados no artigo não se traduzem imediatamente em largura de árvore.

\sqrt{n}

$\sqrt{n}$

Mateus de Oliveira Oliveira

Acredito que os gráficos universais para árvores construídas por Chung e Graham 1983 têm largura de árvore . Ou, para um exemplo um pouco mais simples, mas semelhante, considere os fechamentos transitivos de árvores binárias balanceadas. $\Theta(\log n)$

No entanto, também há um resultado negativo aqui. Todos os exemplos que você dá de famílias de gráficos interessantes são fechados por menores ou muito estreitamente relacionados a famílias fechados a menores. Porém, uma família de grafos fechados menores contém todos os gráficos planares (e, portanto, possui uma largura máxima de árvore ) ou tem um menor plano proibido (e, portanto, limita a largura da árvore). $\Theta(\sqrt n)$

David Eppstein
fonte

Classes de gráficos com largura de árvore superconstante

Respostas: