Qual é o algoritmo polinomial mais simples para PLANARIDADE?

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.)$K_5$$K_{3,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.

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.

Primeiro, dividimos o gráfico em três componentes conectados, como mencionado por Chandra Chekuri.

1. Divida o gráfico em componentes conectados.
2. $v$$G_i$$G_i-v$
3. $v,u$$G_i$$G_i-\{ v,u \}$

$G$

1. $C$$G$
2. $C$$D$
3. $D$
4. $U$$G-V(C)$$D$$G[U\cup V(C)]$$G$$F$$D$$G[U\cup V(C)]$$C'$$F$$G$$C'$$C$$C'$
5. $G$$G$

Observações:

• Argumentar que a incorporação de mola de Tutte fornece uma incorporação plana não é simples. Gostei da apresentação no livro de Edelsbrunner e Harer, Topologia Computacional, mas é apenas para triangulações. Colin de Verdiere discute a incorporação de primavera em http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , seção 1.4. Uma referência geral é Linial, Lovász, Wigderson: elásticos, revestimentos convexos e conectividade gráfica. Combinatorica 8 (1): 91-102 (1988).
• Resolver um sistema linear de equações em um número polioial de operações aritméticas é fácil através da eliminação gaussiana. Resolvê-lo usando um número polinomial de bits não é tão fácil.

O algoritmo de Boyer e Myrvold é considerado um dos mais avançados algoritmos de teste de planaridade

Na aresta de corte: planaridade simplificada de O (n) por adição de aresta por Boyer e Myrvold.

Este capítulo do livro examina muitos algoritmos de teste de planaridade e espero que você encontre um algoritmo bastante simples.

E o algoritmo de Hopcroft e Tarjan de 1974 {1} ?

{1} Hopcroft, John e Robert Tarjan. "Teste de planaridade eficiente." Journal of the ACM (JACM) 21.4 (1974): 549-568.

Dois algoritmos, ambos no LogSpace

1. Eric Allender e Meena Mahajan - A complexidade dos testes de planaridade
2. Samir Datta e Gautam Prakriya - Revisão da Planaridade

O segundo é muito mais simples que o primeiro.