TY - GEN
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:
Acknowledgments. This research was supported in part by the National Science Foundation under grant 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 - 2011
Y1 - 2011
N2 - We study methods for drawing trees with perfect angular resolution, i.e., with angles at each vertex, 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 vertex, 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.
UR - http://www.scopus.com/inward/record.url?scp=79952259660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952259660&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-18469-7_17
DO - 10.1007/978-3-642-18469-7_17
M3 - Conference contribution
AN - SCOPUS:79952259660
SN - 9783642184680
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 183
EP - 194
BT - Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
T2 - 18th International Symposium on Graph Drawing, GD 2010
Y2 - 21 September 2010 through 24 September 2010
ER -