Baumzerlegung für planare Graphen

Zuerst auf math.SE ohne Antworten gefragt .

1. Angenommen, ich habe ein planares Diagramm mit einer planaren Einbettung. Wie finde ich die Baumzerlegung?
2. Was ist die optimale Baumzerlegung eines by- d- Quadratgitters? Nicht ganz sicher, wie man "optimal" definiert, aber es sollte zwischen Zersetzung mit einem großen Beutel und Zersetzung mit vielen großen Beuteln unterschieden werden.$d$$d$

Wenn Sie wirklich eine gute Eliminierungsreihenfolge wünschen, suchen Sie möglicherweise nach einer generalisierten verschachtelten Dissektion . Dies ist die Strategie, die die guten Separatoren einer planaren Graphen zu geben ausnutzt Algorithmen für die Gauß - Elimination, Determinante, etc. für Matrices aus Richtung planar Graphen.$O(n^{\omega/2})$

Für die erste Frage ist offen, ob das Finden einer Baumzerlegung für planare Graphen in Polynomzeit erfolgen kann. Der beste Approximationsalgorithmus kann der RatCatcher- Algorithmus von Seymour und Thomas sein, der die Verzweigungsbreite des planaren Graphen berechnet , sodass er ein Approximationsverhältnis von 1,5 durch die Beziehung zwischen Verzweigungsbreite und Baumbreite aufweist.

$k \times k$

$k \times k$$k$

$k+1$$k(k-1)$

Wenn Sie keine optimale Baumzerlegung wünschen, können Sie eine Baumzerlegung erstellen, indem Sie Trennzeichen rekursiv berechnen.