Texto completo
| |
| Autor(es): |
Alexandre Noma
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2003-05-09 |
| Orientador: | Cristina Gomes Fernandes |
| Resumo | |
O problema da planaridade consiste em: dado um grafo G, decidir se G é ou não é planar. A resposta deve vir acompanhada de uma justificativa. Se G é planar, então uma justificativa é uma representação de um desenho de G no plano sem cruzamento de arestas. Se G não é planar, então uma justificativa é uma subdivisão do 'K IND.3,3' ou do 'K IND. 5' em G. Existem vários algoritmos lineares para testar planaridade. Dois deles são bem conhecidos: o algoritmo proposto por Auslander e Parter [1], posteriormente corrigido por Goldstein [9] (APG), e o algoritmo proposto por Lempel, Even e Cederbaum [12] (LEC). Hopcroft e Tarjan [10] apresentaram em 1974 a primeira implementação linear do algoritmo de APG. Pouco depois, Booth e Lueker apresentaram uma implementação linear do algoritmo de LEC, introduzindo uma nova estrutura de dados chamada PQ-árvore. Recentemente, Shih e Hsu [15] e Boyer e Myrvold [3] publicaram duas implementações lineares do algoritmo de LEC que evitam o uso da PQ-árvore. Este trabalho apresenta uma descrição do algoritmo de LEC e uma descrição da implementação de Shih e Hsu, bem como um estudo comparativo desta implementação com as implementações de Hopcroft e Tarjan, Booth e Lueker e de Boyer e Myrvold (AU) | |
| Processo FAPESP: | 00/03969-2 - Análise experimental de algoritmos para teste de planaridade |
| Beneficiário: | Alexandre Noma |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |