A near-linear area bound for drawing binary trees

T. M. Chan

doi:10.1007/s00453-002-0937-x

A near-linear area bound for drawing binary trees

Research output: Contribution to journal › Article › 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¹+ε) area is always sufficient for an arbitrary constant ε > 0.

Original language	English (US)
Pages (from-to)	1-13
Number of pages	13
Journal	Algorithmica (New York)
Volume	34
Issue number	1
DOIs	https://doi.org/10.1007/s00453-002-0937-x
State	Published - Jan 1 2002
Externally published	Yes

Keywords

Graph drawing
Trees

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-002-0937-x

Library availability

Discover UIUC Full Text

Cite this

@article{719b409cf4504ff58c38e73fc8a7be08,

title = "A 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.",

keywords = "Graph drawing, Trees",

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

year = "2002",

month = jan,

day = "1",

doi = "10.1007/s00453-002-0937-x",

language = "English (US)",

volume = "34",

pages = "1--13",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - A near-linear area bound for drawing binary trees

AU - Chan, T. M.

PY - 2002/1/1

Y1 - 2002/1/1

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.

KW - Graph drawing

KW - Trees

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

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

U2 - 10.1007/s00453-002-0937-x

DO - 10.1007/s00453-002-0937-x

M3 - Article

AN - SCOPUS:0141957132

VL - 34

SP - 1

EP - 13

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

IS - 1

ER -

A near-linear area bound for drawing binary trees

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this