Decomposição de gráficos do gênero um

Os gráficos planares são livres de . Tais gráficos podem ser decomposta em componentes conectado-tri, que são conhecidos por ser ou plana ou componentes. $K_{3,3}$ $K_5$

Existe uma decomposição "agradável" de gráficos do gênero um?

Em seu trabalho seminal sobre menores de gráfico, Roberston e Seymour mostraram que todos os gráficos menores livres podem ser decompostos em uma "soma de cliques" de gráficos "quase planares". Isso, é claro, também se aplica aos gráficos de gênero limitado. Estou procurando decomposições específicas para gráficos do gênero um, para entender melhor suas propriedades estruturais.

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

Isso pode ser útil: arxiv.org/abs/math/0411488

Jeffε 23/03

Ah, obrigado Jeff. Tangencialmente relacionado à pergunta, eu estava intrigado sobre como incorporar o

no toro e não consegui descobrir.

K_{7}

$K_7$

precisa

Há um resultado de decomposição mais forte para famílias de gráficos que excluem um gráfico de cruzamento único como menor (isto é, um gráfico que pode ser desenhado no plano com um único ponto onde as arestas se cruzam). Esses gráficos podem ser decompostos em cliques de gráficos planares e gráficos de largura constante (consulte, por exemplo, "Algoritmos de aproximação para classes de gráficos excluindo gráficos de cruzamento único como menores"). Se houver um gráfico de cruzamento único no conjunto de obstruções do toro, isso o ajudará. (Não estou certo que há embora - e pode haver uma razão muito simples, não pode haver.)

Bart Jansen

Existe uma razão simples para que não haja uma obstrução de passagem única na toroidalidade: todo gráfico de passagem única pode ser desenhado no toro, substituindo a passagem por uma pequena alça.

David Eppstein

Decomposição de gráficos do gênero um

Respostas: