Drawing Trees with Perfect Angular Resolution and Polynomial Area

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} equal to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\pi /d(v)$$\end{document}. We show: Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 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. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 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.

• Publication year

  2010

• Venue

  Discrete & Computational Geometry

• Publication date

  2010-09-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-012-9472-yarXiv 1009.0581
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Usability of Lombardi Graph Drawings

  2012cited by this paper
• The graphs of planar soap bubbles

  2012cited by this paper
• A User Study on Curved Edges in Graph Visualization

  2012cited by this paper
• Planar Lombardi Drawings for Subcubic Graphs

  2012cited by this paper
• Planar Lombardi Drawings of Outerpaths

  2012cited by this paper
• Planar and Poly-arc Lombardi Drawings

  2011cited by this paper
• On Minimum Area Planar Upward Drawings of Directed Trees and Other Families of Directed Acyclic Graphs

  2007cited by this paper
• Simultaneous graph embedding with bends and circular arcs

  2006cited by this paper
• Trees with Convex Faces and Optimal Angles

  2006cited by this paper
• Bubble Tree Drawing Algorithm

  2004cited by this paper
• Curvilinear Graph Drawing Using the Force-directed Method

  2003cited by this paper
• Area-Efficient Order-Preserving Planar Straight-Line Drawings of Ordered Trees

  2003cited by this paper
• Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way

  2002cited by this paper
• Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio

  2002cited by this paper
• Improving Walker's Algorithm to Run in Linear Time

  2002cited by this paper
• Drawing with Fat Edges

  2001cited by this paper
• Area-efficient algorithms for straight-line tree drawings

  2000cited by this paper
• Drawing planar graphs with circular arcs

  1999cited by this paper
• Circular drawings of rooted trees

  1998cited by this paper
• Optimizing area and aspect ration in straight-line orthogonal tree drawings

  1996cited by this paper
• Planar upward tree drawings with optimal area

  1996cited by this paper
• A node‐positioning algorithm for general trees

  1990cited by this paper
• Fast Algorithms for Finding Nearest Common Ancestors

  1984cited by this paper
• Tidier Drawings of Trees

  1981cited by this paper
• Tidy Drawings of Trees

  1979cited by this paper
• Journal of Graph Algorithms and Applications on Balloon Drawings of Rooted Trees

  year unknowncited by this paper
• Journal of Graph Algorithms and Applications Using Graph Layout to Visualize Train Interconnection Data

  year unknowncited by this paper
• Journal of Graph Algorithms and Applications Lombardi Drawings of Graphs

  year unknowncited by this paper

• Aesthetics and comprehension of curved 3D graphs in Virtual Reality

  2023cites this paper
• On the Complexity of Lombardi Graph Drawing

  2023cites this paper
• Angles of Arc-Polygons and Lombardi Drawings of Cacti

  2021influential citation
• Limitations on Realistic Hyperbolic Graph Drawing

  2021cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• The Stub Resolution of 1-Planar Graphs

  2020cites this paper
• Graphs with large total angular resolution

  2019cites this paper
• NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2019cites this paper
• Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings

  2019cites this paper
• NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• Drawing plane triangulations with few segments

  2018cites this paper
• A Universal Slope Set for 1-Bend Planar Drawings

  2017cites this paper
• Universal Slope Sets for 1-Bend Planar Drawings

  2017cites this paper
• 55 GRAPH DRAWING

  2016cites this paper
• 2-D Layout for Tree Visualization: a survey

  2016cites this paper
• Angular Schematization in Graph Drawing

  2015cites this paper
• A Möbius-Invariant Power Diagram and Its Applications to Soap Bubbles and Planar Lombardi Drawing

  2014cites this paper
• Crossings, curves, and constraints in graph drawing

  2014cites this paper
• Graph Drawing

  2013influential citation
• Force-Directed Drawing Algorithms

  2013cites this paper
• Smooth Orthogonal Drawings of Planar Graphs

  2013cites this paper
• Achieving Good Angular Resolution in 3D Arc Diagrams

  2013cites this paper
• On a conjecture of Lovász on circle-representations of simple 4-regular planar graphs

  2012cites this paper
• Spring Embedders and Force Directed Graph Drawing Algorithms

  2012cites this paper
• On the Usability of Lombardi Graph Drawings

  2012cites this paper
• Force-Directed Graph Drawing Using Social Gravity and Scaling

  2012cites this paper
• The graphs of planar soap bubbles

  2012cites this paper
• Constrained Graph Drawing

  2012cites this paper
• Angle Optimization of Graphs Embedded in the Plane

  2012cites this paper
• Planar Lombardi Drawings for Subcubic Graphs

  2012cites this paper
• Planar Lombardi Drawings of Outerpaths

  2012cites this paper
• Force-Directed Lombardi-Style Graph Drawing

  2011cites this paper
• Planar and Poly-arc Lombardi Drawings

  2011cites this paper
• Drawing a tree as a minimum spanning tree approximation

  2010cites this paper
• Journal of Graph Algorithms and Applications Smooth Orthogonal Layouts

  year unknowncites this paper
• Journal of Graph Algorithms and Applications Lombardi Drawings of Graphs

  year unknowncites this paper