Sobre Grafos EPG e Imersões de Árvores em Grades

• Ano de defesa: 2024
• Autor(a) principal: Luca, Vitor Tocci Ferreira de
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: EPG graphs; Rectangular grids; Triangular grids; Bend-number; Embeddings; Grafos EPG; Grades retangulares; Grades triangulares; Número de dobra; Imersões; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/23365

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.