José Coelho de Pina
IME-USP
Sexta-feira, 14 de março de 2003, 15:15
Sala 268, Bloco A, IME-USP
Resumo:
Um grafo é planar se ele pode ser desenhado no plano de tal forma que vértices são representados por pontos e arestas são representadas por curvas que não se 'cruzam'.
Neste seminário descreveremos o algoritmo de Lempel, Even e Cederbaum (LEC) que decide se um grafo dado é planar. O algoritmo de LEC examina cada vértice do grafo, um após o outro, em uma certa ordem. Em cada iteração, o algoritmo procura acrescentar o vértice sendo examinado ao desenho plano do subgrafo induzido pelos vértices já examinados.
A descrição do algoritmo de LEC utilizará o conceito de moldura, proposto por Robin Thomas. Existem pelo menos três implementações deste algoritmo que gastam tempo linear: Booth e Lueker (1976), Shih e Hsu (1999) e Boyer e Myrvold (1999).
O seminário tem a pretenção de separar (o máximo possível) o algoritmo abstrato das (muito importantes!) tecnicalidades de suas implementações que consomem tempo linear; uma delas será o objeto do próximo seminário.
Este seminário é baseado na dissertação de mestrado de Alexandre Noma.