Cristina Gomes Fernandes
IME-USP
Sexta-feira, 21 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 a implementação de Shih e Hsu (algoritmo de SH) do algoritmo de Lempel, Even e Cederbaum (LEC), apresentado no seminário passado. A implementação decide se um grafo dado é ou não planar em tempo linear e pode ser estendida para apresentar um certificado para a resposta (um desenho plano ou um subgrafo de Kuratowski) também em tempo linear.
O algoritmo de SH examina cada vértice do grafo, um após o outro, de acordo com uma busca em profundidade no grafo. 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 SH utilizará o conceito de moldura, proposto por Robin Thomas. A estrutura de dados utilizada para armazenar uma moldura foi batizada por Shih e Hsu de PC-árvore, e é uma variante da conhecida PQ-árvore.
No seminário, serão apresentadas as estruturas de dados utilizadas e será mostrado como estas são atualizadas e utilizadas para efetuar as principais tarefas embutidas no algoritmo de LEC (a busca dos terminais e a busca por uma XY-obstrução).
Este seminário baseia-se na dissertação de mestrado de Alexandre Noma.