How to Fit a Tree in a Box

Hugo Akitaya; Maarten Löffler; Irene Parada

How to Fit a Tree in a Box

Hugo Akitaya
, Maarten Löffler
, Irene Parada

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study compact straight-line embeddings of trees. We show that perfect balanced binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $sqrt n$ by $sqrt n$ grid. We also show that testing whether a given low-degree tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.

Original language	English
Title of host publication	Proc. 26th Symposium on Graph Drawing
Publication status	Published - 2018

Bibliographical note

(to appear)

Keywords

CG, GRAPH, GD

Cite this

@inproceedings{808a08e2d4fc41c79a70a0cdfa1e0896,

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

abstract = "We study compact straight-line embeddings of trees. We show that perfect balanced binary trees can be embedded optimally: a tree with \$n\$ nodes can be drawn on a \$sqrt n\$ by \$sqrt n\$ grid. We also show that testing whether a given low-degree tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.",

keywords = "CG, GRAPH, GD",

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

note = "(to appear)",

year = "2018",

language = "English",

booktitle = "Proc. 26th Symposium on Graph Drawing",

}

TY - GEN

T1 - How to Fit a Tree in a Box

AU - Akitaya, Hugo

AU - Löffler, Maarten

AU - Parada, Irene

N1 - (to appear)

PY - 2018

Y1 - 2018

N2 - We study compact straight-line embeddings of trees. We show that perfect balanced binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $sqrt n$ by $sqrt n$ grid. We also show that testing whether a given low-degree 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 balanced binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $sqrt n$ by $sqrt n$ grid. We also show that testing whether a given low-degree tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.

KW - CG, GRAPH, GD

M3 - Conference contribution

BT - Proc. 26th Symposium on Graph Drawing

ER -

How to Fit a Tree in a Box

Abstract

Bibliographical note

Keywords

Fingerprint

Cite this