Разложение графов рода один

Планарные графы -бесплатно. Такие графики могут быть разложены на трехсвязные компоненты, которые, как известно, являются либо плоскими, либо компонентами . $K_{3,3}$ $K_5$

Есть ли такая «хорошая» декомпозиция графов рода один?

В своей основополагающей работе над минорами графов Роберстон и Сеймур показали, что каждый несимвольный граф можно разложить на «клик-сумму» «почти плоских» графов. Это, конечно, относится и к графам ограниченного рода. Я ищу разложения, специфичные для графов рода 1, чтобы лучше понять их структурные свойства.

graph-theory co.combinatorics planar-graphs graph-minor Шива Кинтали
источник

Это может быть полезно: arxiv.org/abs/math/0411488

Джеффс

Ах, спасибо, Джефф. Тангенциально связанный с вопросом, я ломал голову над тем, как вставить

в тор, и я не смог понять это.

K_{7}

$K_7$

Джон Мёллер

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

Барт Янсен

Существует простая причина, по которой не может быть препятствия с одним пересечением к тороидальности: каждый граф с одним пересечением можно нарисовать на торе, заменив пересечение маленькой ручкой.

Дэвид Эппштейн

Разложение графов рода один

Ответы: