2026-04-13T03:04:43Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/3758612026-01-21T10:27:10Zcom_2072_1033col_2072_452950

urn:hdl:2117/375861 How to fit a tree in a box Akitaya, Hugo Löffler, Maarten Parada Muñoz, Irene María de À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 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 Springer Nature