Fabiano de S. Oliveira, COPPE/UFRJ – DSc

Esta tese tem como foco o estudo de algumas propriedades estruturais de grafos de intervalo e ordens de intervalo e acerca da complexidade em reconhecer tais propriedades. Em particular, apresentamos os seguintes resultados: (i) fornecemos caracterizações de cliques extremas e grafos representáveis por cliques homogêneas; (ii) introduzimos uma nova dimens˜ao de ordens chamada dimensão linear-intervalar, mostrando sua conexão com o problema de reconhecimento de grafos PI. Mostramos que a dimensão linear-intervalar é um invariante de comparabilidade e descrevemos uma caracterização para grafos PI em termos desta dimensão. Fornecemos exemplos de ordens possuindo dimensão linear-intervalar arbitrária; (iii) provemos o estado-daarte do problema de contagem de intervalos, apresentando os resultados existentes na literatura à respeito; e (iv) fornecemos algoritmos eficientes para a computação da contagem de intervalos de generalizações de grafos de limiar, além de apresentar outras propriedades relacionadas à contagem de intervalos de grafos e ordens.