Existem vários algoritmos que decidem no tempo polinomial se um gráfico pode ser desenhado no plano ou não, mesmo muitos com um tempo de execução linear. No entanto, não consegui encontrar um algoritmo muito simples que se pudesse explicar com facilidade e rapidez na aula e mostraria que PLANARITY está em P. Você conhece algum?
Se necessário, você pode usar o teorema de Kuratowski ou Fary, mas nada profundo, como o teorema do gráfico menor. Observe também que não me importo com o tempo de execução, apenas quero algo polinomial.
Abaixo estão os 3 melhores algoritmos até agora, mostrando uma troca de simplicidade / sem necessidade de teoria profunda.
Algoritmo 1: Usando isso, podemos verificar se um gráfico contém um ou um K 3 , 3 como menor no tempo polinomial, obtemos um algoritmo muito simples usando a teoria profunda. (Observe que essa teoria já usa incorporação de gráficos, como apontado por Saeed, portanto essa não é uma abordagem algorítmica real, apenas algo simples para dizer aos alunos que já conheciam / aceitaram o teorema menor do gráfico.)K5K5K3 , 3K3,3
Algoritmo 2 [baseado na resposta de alguém]: É fácil ver que é suficiente lidar com gráficos de 3 conexões. Para isso, encontre um rosto e aplique o teorema da mola de Tutte.
Algoritmo 3 [recomendado por Juho]: algoritmo Demoucron, Malgrange e Pertuiset (DMP). Desenhe um ciclo, os componentes do gráfico restante são chamados fragmentos, os incorporamos de maneira adequada (enquanto isso cria novos fragmentos). Essa abordagem não usa outros teoremas.
Eu acho que muitos concordam que o algoritmo de tempo polinomial mais simples é o algoritmo Demoucron, Malgrange e Pertuiset (DMP). É um algoritmo que os livros didáticos normalmente cobrem (veja, por exemplo, Gibbons 1985 ou Bondy & Murty 1976). É suficiente apenas decidir a planaridade, ou o algoritmo também deve gerar uma incorporação planar? No IIRC, o documento SODA'99 de Boyer e Myrvold @joro provavelmente se refere a detalhes omissos, especialmente em relação à complexidade do tempo.
— 22414 Juho
Se você deseja que apenas o problema de decisão seja PLANO, não são dois menores proibidos cuja existência pode ser verificada em tempo polinomial o suficiente?
@joro: Sim, é claro que seria uma solução simples, mas eu preferiria evitar o uso de um teorema tão forte.
O algoritmo que mencionei era basicamente o algoritmo de Auslander-Parter. O problema no meu algoritmo foi a parte 7, quando eu disse que podemos bipartirar o gráfico dos componentes. Podemos no algoritmo original, mas no algoritmo que eu disse que precisamos de definições mais precisas de componentes e não estava disposto a explicá-lo em detalhes. A parte recursiva era claramente verdadeira (se podemos executar o passo 7, então terminamos), onde você duvida sobre sua correção. Não atualizei minha resposta porque vi que ela teria cerca de duas páginas e não posso abreviá-la mais e não é bom chamar de simples.
Reduzir para o caso de 3 conexões é conceitualmente simples e deve ser explicado em qualquer caso. Se não estivermos interessados ​​demais em eficiência, a redução para casos com três conexões pode ser feita com facilidade. Verifique todos os cortes de 2 nós.
Vou descrever um algoritmo. Não tenho certeza se qualifica como "fácil" e que algumas das provas não são tão fáceis.