2026-04-13T04:00:23Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Akitaya, Hugo author Löffler, Maarten author Parada Muñoz, Irene María de author 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) À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 How to fit a tree in a box