Zerlegen von Graphen der Gattung eins

15

Planare Graphen sind -frei. Solche Graphen können in dreifach verbundene Komponenten zerlegt werden, von denen bekannt ist, dass sie entweder planare oder K 5 -Komponenten sind.K3,3K5

Gibt es so eine "nette" Zerlegung von Graphen der Gattung eins?

Roberston und Seymour haben in ihrer bahnbrechenden Arbeit zu Graph Minors gezeigt, dass jeder minderjährige Graph in eine "Cliquensumme" von "fast planaren" Graphen zerlegt werden kann. Dies gilt natürlich auch für Graphen der begrenzten Gattung. Ich suche nach Zerlegungen, die spezifisch für die Graphen der ersten Gattung sind, um ihre strukturellen Eigenschaften besser zu verstehen.

graph-theory co.combinatorics planar-graphs graph-minor Shiva Kintali
quelle
Dies kann nützlich sein: arxiv.org/abs/math/0411488
Jeffε
Ah, danke Jeff. Tangential auf die Frage bezogen, hatte ich gerätselt , wie einzubetten auf dem Torus und ich hatte es nicht in der Lage gewesen , um herauszufinden. K7
John Moeller
Es gibt ein besseres Ergebnis für die Zerlegbarkeit von Diagrammfamilien, bei denen ein Diagramm mit einfacher Überkreuzung als untergeordnetes Element ausgeschlossen ist (dh ein Diagramm, das in der Ebene mit einem einzelnen Punkt gezeichnet werden kann, an dem sich die Kanten kreuzen). Solche Graphen können in Cliquen von planaren Graphen und Graphen mit konstanter Breite zerlegt werden (siehe z. B. "Approximationsalgorithmen für Klassen von Graphen mit Ausnahme von einfach gekreuzten Graphen als Minderjährige"). Wenn das Hindernisset für den Torus eine einzelne Kreuzungskurve enthält, kann dies hilfreich sein. (Ich bin nicht sicher, ob es das gibt - und es könnte einen einfachen Grund geben, den es nicht geben kann.)
Bart Jansen
Es gibt einen einfachen Grund, warum es kein Hindernis für die Toroidalität bei einer Kreuzung geben kann: Jeder Graph bei einer Kreuzung kann auf den Torus gezeichnet werden, indem die Kreuzung durch einen kleinen Griff ersetzt wird.
David Eppstein

Antworten:

1

Ich denke, dass Robertson und Seymour gezeigt haben, dass jeder minderjährige Graph in eine "Cliquensumme" von " fast begrenzten Gattungsgraphen " zerlegt werden kann . Die Grundbausteine ​​sind keine ebenen Graphen, sondern Graphen der begrenzten Gattung (Gattung abhängig vom ausgeschlossenen Nebenfach). Ich denke, dass toroidale Graphen nicht weiter zerlegbar sind.

Marcin Kamiński
quelle