Drawing Trees with Perfect Angular Resolution and Polynomial Area

DOI10.1007/978-3-642-18469-7_17MaRDI QIDQ3073671zbMATH OpenOpenAlexFDO

Authors Christian A. Duncan, David Eppstein, Stephen G. Kobourov, Martin Nöllenburg, Michael T. Goodrich

Publication date 11 February 2011

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.0581

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node v equal to 2{pi}/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.

Recommendations

• Drawing trees with perfect angular resolution and polynomial area
• Drawing complete binary trees inside rectilinear polygons
• Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
• scientific article; zbMATH DE number 1974131
• Nearly optimal monotone drawing of trees
• Angle and Distance Constraints on Tree Drawings
• PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA
• Ideal drawings of rooted trees with approximately optimal width
• Graph Drawing

Cited in

(11)

• Complexity analysis of balloon drawing for rooted trees
• On Balloon Drawings of Rooted Trees
• Graph Drawing
• Drawing a tree as a minimum spanning tree approximation
• Pinning balloons with perfect angles and optimal area
• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing
• Angle and Distance Constraints on Tree Drawings
• Force-directed Lombardi-style graph drawing
• Drawing trees with perfect angular resolution and polynomial area
• Voronoi drawings of trees
• Vertex angle and crossing angle resolution of leveled tree drawings

This page was built for publication: Drawing Trees with Perfect Angular Resolution and Polynomial Area

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073671)