1. Home
  2. Universitat Politècnica de Catalunya
  3. E-prints
  4. View Item

How to fit a tree in a box

Author

Akitaya, Hugo

Löffler, Maarten

Parada Muñoz, Irene María de

Other authors

Universitat Politècnica de Catalunya. Departament de Matemàtiques

Publication date

2022-10-01

Share

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.

Peer Reviewed

Postprint (author's final draft)

Document Type

Article

Language

English

Subjects and keywords

À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

Publisher

Springer Nature

Related items

https://link.springer.com/article/10.1007/s00373-022-02558-z

Recommended citation

This citation was generated automatically.

Export

DIDL MARC MARC_CCUC METS OAI_DC ORE QDC RDF

Rights

http://creativecommons.org/licenses/by-nc-nd/4.0/

Open Access

Attribution-NonCommercial-NoDerivatives 4.0 International

This item appears in the following Collection(s)

E-prints [72986]