Sobre Ordens e Grafos de Intervalo - Cerioli, Márcia R.; Oliveira, Fabiano de S.; Szwarcfiter, Jayme L. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2012)
A tese resumida neste trabalho tem como foco o estudo de propriedades estruturais de grafos e ordens de intervalo e a complexidade em reconhecê-las. Em particular, (i) fornecemos caracterizações de cliques extremas e grafos representáveis por cliques homogêneas; (ii) introduzimos uma nova dimensão de ordens chamada dimensão linear-intervalar, mostrando sua conexão com o problema de reconhecimento de grafos PI; (iii) provemos o estado-da-arte do problema de contagem de intervalos, apresentando os resultados existentes na literatura; e (iv) fornecemos algoritmos eficientes para a computação da contagem de intervalos de generalizações de grafos de limiar.