Имеют ли графы «внешнего ограниченного рода» постоянную ширину дерева?

Пусть и обозначим через множество всех графов, которые могут быть вложены в поверхность рода , что все вершины расположены на внешней грани . Например, - это множество внешнепланарных графов. Может ли ширина графов в ограничена сверху некоторой функцией от ?G k k G 0 G k$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

Другое направление, очевидно, не выполняется, поскольку постоянная ширина дерева даже не подразумевает постоянного рода: пусть будет объединением непересекающихся копий . Ширина постоянна, однако ее род равен . n K 3 , 3 H n$H_n$$n$$K_{3,3}$$H_n$$n$

Да.

Добавьте вершину в середине внешней грани, соединенную со всеми вершинами внешней грани; это не меняет род и не уменьшает ширину дерева. Теперь у графа есть очень мелкое дерево поиска в ширину, укорененное в новой вершине (все рядом с ним).

Сформируйте остовное дерево двойственного графа, двойные ребра которого не пересекаются с ребрами первого дерева поиска ширины. Тогда есть множество O (родов) ребер, которые не принадлежат ни одному дереву. Каждое из этих ребер создает короткий цикл (треугольник) вместе с путем в дереве поиска шириной, а разрезание поверхности вдоль этих циклов приводит к плоской поверхности (см. Мою статью «Динамические генераторы топологически вложенных графов»). То есть, если G 'является подграфом входного графа, индуцированного вершинами, которые не являются конечными точками ребер O (рода), то G' является плоским, и его вершины могут быть покрыты гранями O (рода) его плоское вложение (грани, в которые циклы вырезания разрезают исходную внешнюю грань).

Но в плоском графе, в котором все вершины принадлежат k граням, можно удалить другие O (k) ребер (остовное дерево граней), чтобы получить внешний планарный граф. Таким образом, ширина дерева G 'O (род). Если кто-то формирует древовидную декомпозицию G 'с этой шириной, а затем добавляет к каждому пакету вершины, являющиеся конечными точками ребер цикла среза, то результатом является древовидная декомпозиция исходного входного графа с шириной дерева O (род).

Кажется вероятным, что это должно быть где-то в литературе, но я не знаю, где и некоторые быстрые поиски не смогли найти явное утверждение этого точного результата. Однако более общее утверждение содержится в другой моей статье: в «Диаметре и ширине дерева в семействах минор-замкнутых графов», среди прочего, я доказываю, что графы ограниченного рода с ограниченным диаметром имеют ограниченную ширину дерева. В этом случае (добавляя эту дополнительную вершину в пределах внешней грани) диаметр можно принять равным максимум двум.