Near-linear area bound for drawing binary trees

Timothy M. Chan

Near-linear area bound for drawing binary trees

Research output: Contribution to conference › Paper › peer-review

Abstract

We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O(n^1+ε) area is always sufficient for an arbitrary constant ε>0.

Original language	English (US)
Pages	161-168
Number of pages	8
State	Published - 1999
Externally published	Yes
Event	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999

Other

Other	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
City	Baltimore, MD, USA
Period	1/17/99 → 1/19/99

ASJC Scopus subject areas

Software
Mathematics(all)

Library availability

Discover UIUC Full Text

Cite this

@conference{0521d9ded6fb43be92467e14a76e38ae,

title = "Near-linear area bound for drawing binary trees",

abstract = "We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O(n1+ε) area is always sufficient for an arbitrary constant ε>0.",

author = "Chan, {Timothy M.}",

year = "1999",

language = "English (US)",

pages = "161--168",

note = "Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 17-01-1999 Through 19-01-1999",

}

TY - CONF

T1 - Near-linear area bound for drawing binary trees

AU - Chan, Timothy M.

PY - 1999

Y1 - 1999

N2 - We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O(n1+ε) area is always sufficient for an arbitrary constant ε>0.

AB - We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O(n1+ε) area is always sufficient for an arbitrary constant ε>0.

UR - http://www.scopus.com/inward/record.url?scp=0032784734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032784734&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032784734

SP - 161

EP - 168

T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 1999 through 19 January 1999

ER -

Near-linear area bound for drawing binary trees

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this