TY - JOUR
T1 - Drawing Trees with Perfect Angular Resolution and Polynomial Area
AU - Duncan, Christian A.
AU - Eppstein, David
AU - Goodrich, Michael T.
AU - Kobourov, Stephen G.
AU - Nöllenburg, Martin
N1 - Funding Information:
This research was supported in part by the National Science Foundation under grants CCF-0545743, CCF-1115971 and CCF-0830403, by the Office of Naval Research under MURI Grant N00014-08-1-1015, and by the German Research Foundation under Grant NO 899/1-1.
PY - 2013/3
Y1 - 2013/3
N2 - We study methods for drawing trees with perfect angular resolution, i. e., with angles at each node v equal to 2π /d(v). We show: 1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.
AB - We study methods for drawing trees with perfect angular resolution, i. e., with angles at each node v equal to 2π /d(v). We show: 1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.
KW - Circular-arc drawings
KW - Lombardi drawings
KW - Perfect angular resolution
KW - Polynomial area
KW - Straight-line drawings
KW - Tree drawings
UR - http://www.scopus.com/inward/record.url?scp=84873733654&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873733654&partnerID=8YFLogxK
U2 - 10.1007/s00454-012-9472-y
DO - 10.1007/s00454-012-9472-y
M3 - Article
AN - SCOPUS:84873733654
SN - 0179-5376
VL - 49
SP - 157
EP - 182
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 2
ER -