On Embedding Trees in Grids
Abstract
We are interested in embedding trees T with maximum degree at most 4 in a rectangular grid, such that the vertices of T correspond to grid points, while edges of T correspond to non-intersecting straight segments of the grid lines. The aim is to minimize the maximum number of bends of a path of T. We provide a quadratic-time algorithm for this problem. By applying this algorithm, we obtain an upper bound on the number of bends of EPG representations of graphs that are in both the classes of VPT and EPT.
Keywords:
EPG graphs, Grid embedding, Bending number
References
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.
Published
2020-06-30
How to Cite
DE LUCA, Vitor Tocci Ferreira; OLIVEIRA, Fabiano de Souza; SZWARCFITER, Jayme Luiz.
On Embedding Trees in Grids. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
