Caracterizações de Grafos de Interseção de Triângulos

Um grafo é PI quando é grafo de interseção de uma família de triângulos com um vértice pertencente a uma reta horizontal e os outros dois vértices pertencentes a uma segunda reta paralela, não-coincidente e abaixo da primeira. O reconhecimento da classe dos grafos PI é um problema em aberto. Neste trabalho, apresentamos a classe dos grafos PI e classes relacionadas sob um ponto de vista unificado, exibindo a hierarquia de inclusão entre elas. Como resultados, mostramos que as classes dos grafos PI* e dos grafos de trapézios simples são incomparáveis. Além disso, apresentamos quatro caracterizações de grafos PI. Uma delas, juntamente com uma conjectura, estabelece que os grafos PI podem ser reconhecidos eficientemente.