Estou procurando referências para o seguinte problema: dados inteiros e , enumere todos os gráficos planares não isomórficos em vértices e largura de árvore . Eu estou interessado tanto em resultados teóricos e práticos, mas principalmente algoritmos práticos que são possíveis de código e executados para como valores grandes quanto possível de e (acho e ). Se você já tem uma resposta, ignore as divagações abaixo.
A abordagem a seguir funciona bem para enumerar todos os gráficos não isomórficos em vértices e largura da árvore (ou seja, quando a restrição de planaridade é eliminada):
(a) Enumere todos os gráficos não isomórficos nos vértices e largura da árvore .
(b) Para cada vértice em vértices e largura da árvore , cada clique em vértices em e todo subconjunto de arestas em , faça partir de adicionando um novo vértice adjacente a . Adicione à lista de grahs em vértices e largura da árvore .
(c) Apare removendo cópias do mesmo gráfico.
Uma maneira tentadora de estender isso para enumerar gráficos planares de largura de árvore é simplesmente filtrar os gráficos não planares a cada iteração. Infelizmente, isso não gera todos os gráficos planares de largura de árvore ≤ k (por exemplo, porque apenas enumera gráficos com 4 degenerados).
É claro que poderíamos enumerar todos os gráficos em vértices e largura de árvore ≤ k e filtrar apenas os não-planos, mas isso não permite explorar que a maioria dos gráficos não é plana e parece muito sub-ideal.
Respostas:
Existe um bom software que gera pequenos gráficos planares com relação ao isomorfismo, o que pode ajudar. Como vejo, um dos problemas era gerar gráficos planares não isomórficos e a maioria desses gráficos planares (em menos de 15 vértices) são de pequena largura de árvore.
fonte
Um limite superior fácil para quantas entradas é necessário armazenar é vezes o número de gráficos enumerados, mas esse é um limite pessimista. Para a maioria dos gráficos de largura de árvore k, a maioria dos subconjuntos de tamanho k não pode ser agrupada, por exemplo, uma grade possui apenas possíveis agrupamentos.(nk) k×n n⋅3k−1
Acredito que isso funcionará tão bem quanto o algoritmo para gráficos não planares, pois para cada par G, B obtemos um gráfico ao fazer B uma clique, a maioria desses gráficos não é isomórfica.
Existem vários truques que podemos aplicar para acelerar isso, eu sugiro olhar para: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf
fonte