Классы графов с суперконстантной шириной дерева

10

Существует несколько интересных классов графов с ограниченной шириной дерева. Например, деревья (treewidth 1), последовательные параллельные графы (treewidth 2), внешнепланарные графы (treewidth 2), -утерплоские графы (treewidth O (k)), графы ширины ветви k (treewidth O (k)), .. ,kk

Вопрос: Существуют ли примеры интересных классов графов, ширина которых не ограничена константой, а низкорастущей функцией?

  1. Существуют ли хорошо известные классы графов с древовидной шириной ?O(loglogn)
  2. Существуют ли хорошо известные классы графов с шириной дерева ?O(logn)

Я хотел бы также быть заинтересованы в классах графов с древесная ширина или O ( лог - лог . . . П ) , где логарифм повторяется постоянное число раз.O(logkn)O(loglog...n)

Obs: Конечно, легко создать искусственные семейства графов с заданной шириной дерева, например, семействоO(logn)×nсетки. Поэтому я в первую очередь ищу семейство графов, которые были изучены в других разделах теории графов и которые имеют ширину дерева или O ( log log n ) , но непостоянную ширину дерева.O(logn)O(loglogn)

Матеус де Оливейра Оливейра
источник
3
Незначительные свободные графы (планарные ++) имеют ширину дерева O((n))O(logn)
nO(logn)n

Ответы:

14

Θ(logn)

Θ(n)

Дэвид Эппштейн
источник