Grid straight-line embeddings of trees with a minimum number of bends per path
Por:
Luca V.T.F., Marin, N., Oliveira, F. S., Ramirez-Vigueras, A., Sole-Pi, O., Szwarcfiter, J. L., Urrutia, J.
Publicada:
1 mar 2022
Resumen:
A grid embedding of a tree T whose vertices have degree at most four is
an embedding in which the vertices of T are represented by points with
integer coordinates, and the edges are represented by interior-disjoint
horizontal or vertical line segments joining pairs of adjacent vertices
in T. In any such embedding, a path of T may bend several times. In this
paper we obtain a linear-time algorithm that given a tree T finds a grid
embedding of T that minimizes the maximum number of times any path of T
bends. All of the results presented here generalize easily to lattice
embeddings of trees in higher dimensions. (C) 2021 Elsevier B.V. All
rights reserved.
Filiaciones:
Luca V.T.F.:
Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Brazil
Marin, N.:
Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México, Mexico
(Corresponding Author), Univ Nacl Autonoma Mexico, Posgrad Ciencia & Ingn Computac, Mexico City, DF, Mexico
Univ Nacl Autonoma Mexico, Posgrad Ciencia & Ingn Computac, Mexico City, DF, Mexico
Oliveira, F. S.:
Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Brazil
Univ Estado Rio De Janeiro, Inst Matemat & Estat, Rio De Janeiro, Brazil
Ramirez-Vigueras, A.:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
Sole-Pi, O.:
Facultad de Ciencias, Universidad Nacional Autónoma de México, Mexico
Univ Nacl Autonoma Mexico, Fac Ciencias, Mexico City, DF, Mexico
Szwarcfiter, J. L.:
COPPE, NCE, IM, Universidade Federal do Rio de Janeiro, Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil
Univ Estado Rio De Janeiro, Inst Matemat & Estat, Rio De Janeiro, Brazil
Univ Fed Rio Janeiro, COPPE, NCE, IM, Rio De Janeiro, Brazil
Urrutia, J.:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
|