1. Inici
  2. Universitat Politècnica de Catalunya
  3. E-prints
  4. Visualitza l'element

How to fit a tree in a box

Autor/a

Akitaya, Hugo

Löffler, Maarten

Parada Muñoz, Irene María de

Altres autors/es

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

Data de publicació

2022-10-01

Compartir

Resum

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)

Tipus de document

Article

Llengua

Anglès

Matèries i paraules clau

À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

Publicat per

Springer Nature

Documents relacionats

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

Citació recomanada

Aquesta citació s'ha generat automàticament.

Exportar

DIDL MARC MARC_CCUC METS OAI_DC ORE QDC RDF

Drets

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

Open Access

Attribution-NonCommercial-NoDerivatives 4.0 International

Aquest element apareix en la col·lecció o col·leccions següent(s)

E-prints [73034]