Sobre a caracterização de grafos de visibilidade de leques convexos

Grafos de visibilidade entre vertices de poligonos sao estruturas que resumem as informacoes de visibilidade de tais vertices. Existem tres relevantes problemas relativos a grafos de visibilidade: caracterizacao, reconhecimento e reconstrucao. O problema da caracterizacao consiste em encontrar um conjunto de condicoes necessarias e suficientes para a classe de grafos de visibilidade. A procura de uma forma algoritmica para se reconhecer quando um grafo e de visibilidade define o problema de reconhecimento. O problema de reconstrucao trata da questao de se reconstruir um poligono a partir de um grafo de visibilidade de tal forma que este seja isomorfo ao grafo de visibilidade do poligono. Neste trabalho, abordamos estes problemas para uma subclasse destes grafos: grafos de visibilidade de leques convexos. Dois resultados principais sao apresentados nesse trabalho. O primeiro deles e um conjunto de tres condicoes necessarias que um grafo de visibilidade de um leque convexo deve satisfazer. Adicionalmente, mostramos que estas condicoes sao necessarias e suficientes para grafos de visibilidade de pseudo-leques convexos. Um resultado colateral deste processo e a equivalencia entre grafos de visibilidade entre vertices, e grafos de visibilidade vertice-aresta, para leques convexos em posicao geral. O segundo resultado consiste em que podemos reduzir o problema de reconstrucao de poligonos unimonotonos para o mesmo problema para leques convexos. Abstract