On Embedding Trees in Grids - de Luca, Vitor Tocci Ferreira; Oliveira, Fabiano de Souza; Szwarcfiter, Jayme Luiz (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2020.11082, 2020)
Estamos interessados em imergir árvores T com grau máximo limitado a 4 em uma grade retangular, de modo que os vértices de T correspondam a pontos da grade, enquanto que as arestas de T correspondam a segmentos retos não intersectantes das retas da grade. O objetivo é minimizar o número máximo de dobras de um caminho de T. Fornecemos um algoritmo de tempo quadrático para esse problema. Aplicando esse algoritmo, obtemos um limite superior para o número de dobras de representações EPG de grafos que pertencem à interseção das classes VPT e EPT.