Caracterizações de Grafos de Interseção de Triângulos - Cerioli, Márcia R.; Oliveira, Fabiano de S.; Szwarcfiter, Jayme L. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2007)
Um grafo é um grafo PI se é o grafo de interseção de uma família de triângulos entre duas retas paralelas. O problema do reconhecimento da classe dos grafos PI está em aberto há 20 anos. Apresentamos um estudo desta classe enfocando aspectos estruturais e computacionais, visando a sua solução. Como principais resultados, relacionamos os grafos PI ao estudo de dimensão de ordens e mostramos que uma dimensão especial definida é um invariante de comparabilidade, resultado mais forte que o análogo para a bem conhecida dimensão intervalar. Formulamos também uma conjectura que se verdadeira implica no reconhecimento eficiente dos grafos PI. Analisamos esta conjectura de forma teórica e computacional, apontando evidências para sua veracidade.