Sobre Grafos EPG e Imersões de Árvores em Grades - Luca, Vitor Tocci Ferreira de (2024)
Neste trabalho, mostramos que são B2-EPG os grafos nos quais todo bloco é B1-EPG e toda articulação é universal nos blocos aos quais pertence. Estendemos a prova para mostrar que os grafos cacto são B1-EPG. Também mostramos um algoritmo de tempo linear, para construir modelos L-EPG de grafos nos quais todo bloco é L-EPG e toda articulação é universal nos blocos aos quais pertence, concluindo que os grafos bloco são L-EPG. O último resultado fornece uma representação alternativa L-EPG para árvores. Além disso, apresentamos um algoritmo para imergir uma árvore T com ∆(T)≤ 4 em uma grade retangular, de forma que o número máximo de dobras em todos os caminhos de T seja minimizado. Também descrevemos como construir s-modelos com k dobras, tendo o menor número de vértices possível para qualquer k ≥ 0. Além disso, os s-modelos produzidos pelo nosso algoritmo foram empregados para construir modelos EPG de grafos VPT ∩ EPT, fornecendo um limite superior para o número de dobra de tais grafos. Por fim, introduzimos uma nova classe de grafos, EPGt, e fornecemos uma caracterização de representações com no máximo uma dobra de cliques e ciclos de 4 vértices nessas grades, estendendo os resultados análogos para os grafos EPG.