dc.contributor
Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor.author
Akitaya, Hugo
dc.contributor.author
Löffler, Maarten
dc.contributor.author
Parada Muñoz, Irene María de
dc.date.issued
2022-10-01
dc.identifier
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.
dc.identifier
https://arxiv.org/abs/1808.10572
dc.identifier
https://hdl.handle.net/2117/375861
dc.identifier
10.1007/s00373-022-02558-z
dc.description.abstract
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.
dc.description.abstract
Peer Reviewed
dc.description.abstract
Postprint (author's final draft)
dc.format
application/pdf
dc.publisher
Springer Nature
dc.relation
https://link.springer.com/article/10.1007/s00373-022-02558-z
dc.rights
http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights
Attribution-NonCommercial-NoDerivatives 4.0 International
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
dc.subject
Trees (Graph theory)
dc.subject
Upward drawing
dc.subject
Area requirement
dc.subject
Arbres (Teoria de grafs)
dc.subject
Grafs, Teoria de
dc.title
How to fit a tree in a box
