2026-04-14T05:27:31Zhttps://recercat.cat/oai/requestoai:recercat.cat:2117/3758612026-01-21T10:27:10Zcom_2072_1033col_2072_452950
How to fit a tree in a box
Akitaya, Hugo
Löffler, Maarten
Parada Muñoz, Irene María de
Universitat Politècnica de Catalunya. Departament de Matemàtiques
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Trees (Graph theory)
Graph theory
Binary trees
Graph drawing
Upward drawing
Area requirement
Arbres (Teoria de grafs)
Grafs, Teoria de
We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with n nodes can be drawn on a vn by vn grid. We also show that testing whether a given rooted binary tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.
Peer Reviewed
Postprint (author's final draft)
2022-10-01
Article
Akitaya, H.; Löffler, M.; De Parada, I. How to fit a tree in a box. "Graphs and combinatorics", 1 Octubre 2022, vol. 38, núm. 155, p. 1-11.
1435-5914
https://arxiv.org/abs/1808.10572
https://hdl.handle.net/2117/375861
10.1007/s00373-022-02558-z
eng
https://link.springer.com/article/10.1007/s00373-022-02558-z
http://creativecommons.org/licenses/by-nc-nd/4.0/
Open Access
Attribution-NonCommercial-NoDerivatives 4.0 International
11 p.
application/pdf
Springer Nature