Universitat Politècnica de Catalunya
Universitat Politècnica de Catalunya. Departament de Matemàtiques
2022-10-01
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)
Article
Inglés
À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
Springer Nature
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
E-prints [73034]
