Décomposition des arbres pour les graphes planaires

Première question sur math.SE sans réponse.

1. Supposons que j'ai un graphe planaire, avec une intégration planaire, comment trouver la décomposition des arbres?
2. Quelle est la décomposition arborescente optimale d'une grille carrée by- ? Je ne sais pas trop comment définir «optimal», mais il devrait faire la distinction entre la décomposition avec un grand sac et la décomposition avec de nombreux grands sacs.$d$$d$

Si ce que vous voulez vraiment, c'est un bon ordre d'élimination, vous cherchez peut-être une dissection imbriquée généralisée . C'est la stratégie qui exploite les bons séparateurs d'un graphe plan pour donner des algorithmes pour l'élimination gaussienne, déterminant, etc. pour les matrices provenant de graphes planaires.$O(n^{\omega/2})$

Pour la première question, il est clair si la recherche d'une décomposition d'arbre pour les graphes planaires peut être effectuée en temps polynomial. Le meilleur algorithme d'approximation peut être l' algorithme RatCatcher de Seymour et Thomas, qui calcule la largeur de branche du graphe planaire, il a donc un rapport d'approximation de 1,5 par la relation entre largeur de branche et largeur d'arbre.

Pour le second, nous avons le théorème suivant sur la largeur d'arbre de grilles:$k \times k$

Théorème. Une grille a une largeur d'arbre .$k \times k$$k$

Et les sacs peuvent être pris avec la taille , avec un total de sacs. Je ne sais pas si c'est ce que vous voulez, alors n'hésitez pas à le faire si vous modifiez la définition de "optimal".$k+1$$k(k-1)$

Si vous ne voulez pas une décomposition d'arbre optimale, vous pouvez créer une décomposition d'arbre en calculant les séparateurs de manière récursive.