Haben die Graphen der äußeren Gattung eine konstante Baumbreite?

Sei und bezeichne mit G k die Menge aller Graphen, die auf einer Oberfläche der Gattung k so eingebettet werden können, dass sich alle Eckpunkte auf der Außenseite befinden . Zum Beispiel ist G 0 die Menge der äußeren ebenen Graphen. Kann die Baumbreite von Graphen in G k durch eine Funktion von k nach oben begrenzt werden ?$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

Die andere Richtung gilt offensichtlich nicht, da konstante Baumbreite nicht einmal konstante Gattung bedeutet: Sei die Vereinigung von n disjunkten Kopien von K 3 , 3 . Die Baumbreite von H n ist konstant, ihre Gattung ist jedoch n .$H_n$$n$$K_{3,3}$$H_n$$n$

Ja.

Fügen Sie einen Scheitelpunkt in der Mitte der Außenfläche hinzu, der mit allen Scheitelpunkten in der Außenfläche verbunden ist. Dies ändert nichts an der Gattung und verringert auch nicht die Baumbreite. Jetzt hat das Diagramm einen Suchbaum mit sehr geringer Breite, der auf dem neuen Scheitelpunkt verwurzelt ist (alles grenzt daran an).

Bilden Sie einen übergreifenden Baum des dualen Graphen, dessen duale Kanten von den Kanten des breitesten ersten Suchbaums getrennt sind. Dann gibt es eine Reihe von O-Kanten (Gattungskanten), die zu keinem der Bäume gehören. Jede dieser Kanten induziert einen kurzen Zyklus (ein Dreieck) zusammen mit einem Pfad im ersten Suchbaum, und das Schneiden der Oberfläche entlang dieser Zyklen erzeugt eine ebene Oberfläche (siehe meine Arbeit "Dynamische Generatoren topologisch eingebetteter Graphen"). Das heißt, wenn G 'der Teilgraph des Eingabegraphen ist, der durch die Scheitelpunkte induziert wird, die keine Endpunkte der O-Schnittkanten (Gattung) sind, dann ist G' planar und seine Scheitelpunkte können durch O-Flächen (Gattung) seiner bedeckt werden Planare Einbettung (die Flächen, in die die Schnittzyklen die ursprüngliche Außenfläche schneiden).

In einem ebenen Graphen, in dem alle Scheitelpunkte zu k Flächen gehören, kann man andere O (k) -Kanten (einen übergreifenden Baum der Flächen) entfernen, um einen äußeren ebenen Graphen zu erhalten. Die Baumbreite von G 'ist also O (Gattung). Bildet man eine Baumzerlegung von G 'mit dieser Breite und addiert dann zu jedem Sack die Eckpunkte, die Endpunkte der Schnittzykluskanten sind, ergibt sich eine Baumzerlegung des ursprünglichen Eingabegraphen mit der Baumbreite O (Gattung).

Es scheint wahrscheinlich, dass dies bereits irgendwo in der Literatur steht, aber ich weiß nicht, wo und einige schnelle Suchen haben es nicht geschafft, eine explizite Aussage über dieses genaue Ergebnis zu finden. Eine allgemeinere Aussage findet sich jedoch in einer anderen Arbeit von mir: In "Durchmesser und Baumbreite in klein geschlossenen Graphenfamilien" beweise ich unter anderem, dass begrenzte Gattungsgraphen mit begrenztem Durchmesser die Baumbreite begrenzt haben. In diesem Fall kann der Durchmesser (durch Hinzufügen dieses zusätzlichen Scheitelpunkts innerhalb der Außenfläche) mit höchstens zwei angenommen werden.