How to Fit a Tree in a Box

Hugo Akitaya; Maarten Löffler; Irene Parada

doi:10.1007/s00373-022-02558-z

How to Fit a Tree in a Box

Hugo Akitaya, Maarten Löffler, Irene Parada

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Article number	155
Pages (from-to)	1-11
Number of pages	11
Journal	Graphs and Combinatorics
Volume	38
DOIs	https://doi.org/10.1007/s00373-022-02558-z
Publication status	Published - 5 Sept 2022

Keywords

Binary trees
Graph drawing
Upward drawing
Area requirement
CG
GRAPH
GD

Access to Document

10.1007/s00373-022-02558-z

s00373-022-02558-zFinal published version, 548 KBLicence: Taverne

Cite this

@article{a5c7fdbc91924946aba7c21c8918a05d,

title = "How to Fit a Tree in a Box",

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",

author = "Hugo Akitaya and Maarten L{\"o}ffler and Irene Parada",

note = "(to appear)",

year = "2022",

month = sep,

day = "5",

doi = "10.1007/s00373-022-02558-z",

language = "English",

volume = "38",

pages = "1--11",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer",

}

TY - JOUR

T1 - How to Fit a Tree in a Box

AU - Akitaya, Hugo

AU - Löffler, Maarten

AU - Parada, Irene

N1 - (to appear)

PY - 2022/9/5

Y1 - 2022/9/5

N2 - 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.

AB - 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.

KW - Binary trees

KW - Graph drawing

KW - Upward drawing

KW - Area requirement

KW - CG

KW - GRAPH

KW - GD

U2 - 10.1007/s00373-022-02558-z

DO - 10.1007/s00373-022-02558-z

M3 - Article

SN - 0911-0119

VL - 38

SP - 1

EP - 11

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

M1 - 155

ER -

How to Fit a Tree in a Box

Abstract

Keywords

Access to Document

Fingerprint

Cite this