Décomposition des graphiques du genre 1

15

Les graphes planaires sont . Ces graphiques peuvent être décomposés en composants tri-connectés, qui sont connus pour être des composants plans ou .K3,3K5

Existe-t-il une décomposition aussi "sympa" des graphes du genre un?

Dans leur travail séminal sur les mineurs de graphes, Roberston et Seymour ont montré que chaque graphe sans mineur peut être décomposé en une «somme clique» de graphes «presque planaires». Ceci, bien sûr, s'applique également aux graphiques de genre borné. Je recherche des décompositions spécifiques aux graphes du genre un, pour mieux comprendre leurs propriétés structurelles.

Shiva Kintali
la source
Cela peut être utile: arxiv.org/abs/math/0411488
Jeffε
Ah, merci Jeff. Tangentiellement lié à la question, j'avais été perplexe sur la façon d'intégrer Ksept sur le tore et je n'avais pas été en mesure de le comprendre.
John Moeller
Il y a un résultat de décomposabilité plus fort pour les familles de graphiques qui excluent un graphique à croisement unique comme mineur (c'est-à-dire un graphique qui peut être dessiné dans le plan avec un seul point où les bords se croisent). De tels graphes peuvent être décomposés en cliques de graphes planaires et de graphes à largeur d'arbre constante (voir par exemple "Algorithmes d'approximation pour les classes de graphes excluant les graphes à simple croisement comme mineurs"). S'il y a un graphique à croisement unique dans l'ensemble d'obstruction pour le tore, cela vous aiderait. (Je ne suis pas sûr qu'il y en ait - et il peut y avoir une raison simple à cela.)
Bart Jansen
Il y a une raison simple pour laquelle il ne peut pas y avoir d'obstruction à une traversée à la toroïdalité: chaque graphique à une traversée peut être tracé sur le tore, en remplaçant le croisement par une petite poignée.
David Eppstein

Réponses:

1

Je pense que Robertson et Seymour ont montré que chaque graphique sans mineur peut être décomposé en une "somme de clique" de graphiques de " genre presque limité ". Les blocs de construction de base ne sont pas des graphiques plans mais des graphiques de genre borné (genre dépendant du mineur exclu). Je pense que les graphes toroïdaux ne sont plus décomposables.

Marcin Kamiński
la source