Seminário de Teoria da Computação Cristina Gomes Fernandes - IME-USP Método de Planaridade de Lempel, Even e Cederbaum Sexta-feira, 4 de junho de 2004 Auditório do IC, IC-1, 13:00hs Resumo: O teste de planaridade consiste em decidir se um dado grafo é ou não planar. Apresentaremos uma descrição alternativa e mais didática do método de Lempel, Even e Cederbaum (LEC) para o teste de planaridade. Vários algoritmos bem conhecidos para o teste de planaridade são na verdade implementações diferentes do método de LEC. Descrevemos a seguir os elementos principais da implementação linear do método de LEC proposta por Shih e Hsu e apresentamos os resultados experimentais obtidos da comparação entre esta implementação e outras três (Booth e Lueker, Hopcroft e Tarjan, e Boyer e Myrvold). Este é um trabalho conjunto com J. Boyer, A. Noma e J.C. de Pina.