Gráficos de descomposición del género uno

Los gráficos tienen . Dichos gráficos pueden descomponerse en componentes , que se sabe que son componentes planos o . $K_{3,3}$ $K_5$

¿Existe una descomposición tan "agradable" de los gráficos del género uno?

En su trabajo seminal sobre gráficos menores, Roberston y Seymour demostraron que cada gráfico libre de menores puede descomponerse en una "suma de camarillas" de gráficos "casi planos". Esto, por supuesto, se aplica también a los gráficos de género acotado. Estoy buscando descomposiciones específicas para gráficos del género uno, para comprender mejor sus propiedades estructurales.

graph-theory co.combinatorics planar-graphs graph-minor Shiva Kintali
fuente

Esto puede ser útil: arxiv.org/abs/math/0411488

Jeffε

Ah, gracias Jeff. Tangencialmente relacionado con la pregunta, había estado pensando cómo incrustar

en el toro y no había sido capaz de resolverlo.

K_{7}

$K_7$

John Moeller

Hay un resultado de descomposición más fuerte para las familias de gráficos que excluyen un gráfico de cruce simple como menor (es decir, un gráfico que se puede dibujar en el plano con un solo punto donde se cruzan los bordes). Dichos gráficos se pueden descomponer en cliquesums de gráficos planos y gráficos de ancho de árbol constante (véase, por ejemplo, "Algoritmos de aproximación para clases de gráficos que excluyen los gráficos de cruce simple como menores"). Si hay un gráfico de cruce único en el conjunto de obstrucción para el toro, esto te ayudaría. (Sin embargo, no estoy seguro de que exista, y puede haber una razón simple por la que no puede haber).

Bart Jansen el

Hay una razón simple por la cual no puede haber una obstrucción de un solo cruce a la toroidalidad: cada gráfico de un solo cruce se puede dibujar en el toro, reemplazando el cruce por un pequeño asa.

David Eppstein

Gráficos de descomposición del género uno

Respuestas: