Log In

How to Fit a Tree in a Box

Files

s00373-022-02558-z.pdf (547.63 KB)

Publication date

2022-09-05

Authors

Akitaya, Hugo
Löffler, MaartenISNI 000000039666142X
Parada, Irene

Editors

Advisors

Supervisors

DOI

https://doi.org/10.1007/s00373-022-02558-z

Document Type

Article

Metadata

Show full item record

Collections

Utrecht University Repository
Open Access logo

License

taverne

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 n−−√ by n−−√ 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.

Keywords

Binary trees, Graph drawing, Upward drawing, Area requirement, CG, GRAPH, GD, Taverne

Citation

Akitaya, H, Löffler, M & Parada, I 2022, 'How to Fit a Tree in a Box', Graphs and Combinatorics, vol. 38, 155, pp. 1-11. https://doi.org/10.1007/s00373-022-02558-z

URI

http://hdl.handle.net/1874/431865