Enumerando gráficos planares da largura da árvore limitada

9

Estou procurando referências para o seguinte problema: dados inteiros n e k , enumere todos os gráficos planares não isomórficos em n vértices e largura de árvore k . 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 n e k (acho k5 e n15 ). 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 n vértices e largura da árvore k (ou seja, quando a restrição de planaridade é eliminada):

(a) Enumere todos os gráficos não isomórficos nos vértices n1 e largura da árvore k .

(b) Para cada vértice G em n1 vértices e largura da árvore k , cada clique C em k vértices em G e todo subconjunto S de arestas em C , faça G partir de GS adicionando um novo vértice v adjacente a C . Adicione G à lista L de grahs em n vértices e largura da árvore k .

(c) Apare L 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).kk4

É 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.nk

daniello
fonte
Tem certeza de que deseja implementá-lo e testar o resultado? O número de árvores não isomórficas já é exponencial.
Saeed
@ Saeed: com certeza - para 20 nós, o número de árvores é menor que um milhão, por isso espero que isso seja possível pelo menos para . n15
Daniello
11
que tal começar com gráficos cordais vertex de tamanho máximo de clique k + 1 e remover arestas para torná-lo plano? nk+1
precisa
@Yixin Cao, isso é semelhante à enumeração de gráficos + decomposições em árvore deles (ou seja, o mesmo gráfico é visto uma vez por árvore). Até agora, que tem sido bastante lento (mas alguma otimização um poderia fazer essa abordagem viável)
Daniello
2
@ Daniello, entendo seu ponto de vista, mas você viu esta aplicação: cs.anu.edu.au/~bdm/plantri , eles afirmam que podem gerar gráficos planares de 1 milhão em um segundo (com relação ao isomorfismo). (não é exatamente o que você deseja, porém, para 1-2-3 gráficos planares conectados parece perfeito, não existem muitos gráficos planares conectados 4-5 em 15 vértices).
Saeed #

Respostas:

2

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.

kGGPdvPluGPwPGd+lk

154tt>5

kG

Saeed
fonte
1

G,BGkBkGB

G,BGn1GSBvSBkBvG,BG

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×nn3k1

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

Martin Vatshelle
fonte
Todos os gráficos enumerados não terão largura de caminho limitada em vez de largura de árvore?
Daniello
Eu acho que você está certo. a escolha de B 'é muito limitada.
Martin Vatshelle