Perguntado pela primeira vez em math.SE sem respostas.
- Suponha que eu tenha um gráfico planar, com uma incorporação planar, como encontro a decomposição da árvore?
- O que é a decomposição de árvore ideal de uma -by- grade quadrada? Não sabe ao certo como definir "ideal", mas deve distinguir entre decomposição com uma sacola grande e decomposição com muitas sacolas grandes.
ds.algorithms
graph-theory
graph-algorithms
treewidth
integer-lattice
Yaroslav Bulatov
fonte
fonte
Para a primeira pergunta, está aberto se é possível encontrar uma decomposição em árvore para gráficos planares em tempo polinomial. O melhor algoritmo de aproximação pode ser o algoritmo RatCatcher de Seymour e Thomas, que calcula a largura de ramificação do gráfico planar, portanto, ela tem uma razão de aproximação de 1,5 pela relação entre largura de ramificação e largura de árvore.
fonte
Se você não deseja uma decomposição ideal de árvore, poderá criar uma decomposição de árvore calculando recursivamente os separadores.
fonte