On Embedding Trees in Grids
Resumo
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.
Palavras-chave:
Grafos EPG, Imersão em grades, Número de dobra
Referências
Alcón, L., Gutierrez, M., and Mazzoleni, M. P. (2015). Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs. Discrete Mathematics, 338(1):103–110.
Beck, M. and Storandt, S. (2020). Puzzling grid embeddings. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pages 94–105. SIAM.
Golumbic, M. C. and Jamison, R. E. (1985). Edge and vertex intersection of paths in a tree. Discrete Mathematics, 55(2):151–159.
Liu, Y., Morgana, A., and Simeone, B. (1998). A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Applied Mathematics, 81(1-3):69–91.
Schnyder, W. (1990). Embedding planar graphs on the grid. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pages 138–148.
Beck, M. and Storandt, S. (2020). Puzzling grid embeddings. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pages 94–105. SIAM.
Golumbic, M. C. and Jamison, R. E. (1985). Edge and vertex intersection of paths in a tree. Discrete Mathematics, 55(2):151–159.
Liu, Y., Morgana, A., and Simeone, B. (1998). A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Applied Mathematics, 81(1-3):69–91.
Schnyder, W. (1990). Embedding planar graphs on the grid. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pages 138–148.
Publicado
30/06/2020
Como Citar
DE LUCA, Vitor Tocci Ferreira; OLIVEIRA, Fabiano de Souza; SZWARCFITER, Jayme Luiz.
On Embedding Trees in Grids. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 29-32.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11082.
