Drawing Trees with Perfect Angular Resolution and Polynomial Area

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

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

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

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 (8)

• Force-Directed Lombardi-Style Graph Drawing
• Planar and Poly-arc Lombardi Drawings
• Drawing a tree as a minimum spanning tree approximation
• Vertex angle and crossing angle resolution of leveled tree drawings
• Voronoi drawings of 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
• Pinning Balloons with Perfect Angles and Optimal Area

Recommendations

• Title not available (Why is that?) 👍 👎
• PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA 👍 👎
• Nearly optimal monotone drawing of trees 👍 👎
• Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio 👍 👎
• Drawing trees with perfect angular resolution and polynomial area 👍 👎
• Angle and Distance Constraints on Tree Drawings 👍 👎
• Graph Drawing 👍 👎
• Ideal Drawings of Rooted Trees With Approximately Optimal Width 👍 👎
• Drawing complete binary trees inside rectilinear polygons 👍 👎

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)