Существует несколько интересных классов графов с ограниченной шириной дерева. Например, деревья (treewidth 1), последовательные параллельные графы (treewidth 2), внешнепланарные графы (treewidth 2), -утерплоские графы (treewidth O (k)), графы ширины ветви k (treewidth O (k)), .. ,
Вопрос: Существуют ли примеры интересных классов графов, ширина которых не ограничена константой, а низкорастущей функцией?
- Существуют ли хорошо известные классы графов с древовидной шириной ?
- Существуют ли хорошо известные классы графов с шириной дерева ?
Я хотел бы также быть заинтересованы в классах графов с древесная ширина или O ( лог - лог . . . П ) , где логарифм повторяется постоянное число раз.
Obs: Конечно, легко создать искусственные семейства графов с заданной шириной дерева, например, семействосетки. Поэтому я в первую очередь ищу семейство графов, которые были изучены в других разделах теории графов и которые имеют ширину дерева или O ( log log n ) , но непостоянную ширину дерева.
источник
Ответы:
источник