Decomposição de árvore para gráficos planares

9

Perguntado pela primeira vez em math.SE sem respostas.

  1. Suponha que eu tenha um gráfico planar, com uma incorporação planar, como encontro a decomposição da árvore?
  2. 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.dd
Yaroslav Bulatov
fonte

Respostas:

11

Se o que você realmente deseja é uma boa ordem de eliminação, você pode estar procurando uma dissecção aninhada generalizada . Essa é a estratégia que explora os bons separadores de um gráfico planar para fornecer algoritmos para eliminação gaussiana, determinante, etc., para matrizes provenientes de gráficos planares.O(nω/2)

Jason Morton
fonte
Interessante, encontrei uma grande quantidade de literatura expandindo o método. Se bem entendi, dada ordem de eliminação ideal, decomposição árvore ideal é fácil
Yaroslav Bulatov
13

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.

k×k

k×kk

k+1 1k(k-1 1)

Hsien-Chih Chang 張顯 之
fonte
4

Se você não deseja uma decomposição ideal de árvore, poderá criar uma decomposição de árvore calculando recursivamente os separadores.

Suresh Venkat
fonte