Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 157-182 |
| Number of pages | 26 |
| Journal | Discrete and Computational Geometry |
| Volume | 49 |
| Issue number | 2 |
| DOIs | |
| State | Published - Mar 2013 |
Keywords
- Circular-arc drawings
- Lombardi drawings
- Perfect angular resolution
- Polynomial area
- Straight-line drawings
- Tree drawings
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'Drawing Trees with Perfect Angular Resolution and Polynomial Area'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS