Drawing Trees with Perfect Angular Resolution and Polynomial Area

DOI10.1007/978-3-642-18469-7_17zbMATH Open1311.68113arXiv1009.0581OpenAlexW1937860508MaRDI QIDQ3073671FDOQ3073671

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)

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.

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

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

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)

Cited In (12)

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

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)