Simple Compact Monotone Tree Drawings

Anargyros Oikonomou, Antonios Symvonis

TL;DR

This paper introduces a novel, simple algorithm for creating "monotone" drawings of trees on a grid. Unlike previous methods that required large grids (up to $12n \times 12n$), their algorithm achieves an $n \times n$ grid for rooted trees and even smaller grids for unrooted trees, while also exploring convex and multi-quadrant drawing variations.

What Problem Does This Paper Address?

Creating "monotone" drawings of graphs is a challenging problem in graph theory and computer science. A monotone drawing ensures that for any two vertices, there's a path between them that stays "monotone" with respect to some direction. For trees, specifically, previous algorithms could produce monotone drawings, but often required very large grid sizes, making them impractical for many applications. This paper aims to significantly reduce the grid size required for monotone tree drawings, making them more compact and efficient, while also exploring variations like convex drawings and drawings that span multiple quadrants.

Methods

The core of the paper lies in a new algorithm for drawing rooted ordered trees. The algorithm works by:

  • Angle Assignment (Strategy 1): It recursively assigns angle ranges to vertices. For a vertex $u$ with children $v_1, \dots, v_m$, the angle range of $u$ is split among its children proportionally to the size of their subtrees. This balanced splitting is key to achieving compact drawings.
  • Grid Point Placement (Lemma 2.7): This lemma provides a geometric method to find grid points for child vertices based on their assigned angle ranges, ensuring the drawing properties are maintained.
  • Algorithm 3.1 (One-Quadrant Traditional): This algorithm combines the angle assignment and grid point placement to produce a monotone drawing of a rooted ordered tree within an $n \times n$ grid. It also extends this to produce convex monotone drawings.
  • Extensions for Unrooted and Multi-Quadrant Drawings: The authors further adapt their approach to handle unrooted trees by identifying a "gravity root" and developing algorithms for two-quadrant (up to $(n+1) \times (n+1)$) and four-quadrant (up to $\lceil \frac{n+2}{2} \rceil \times \lceil \frac{n+2}{2} \rceil$) drawings.

Datasets

Not discussed in the paper. The paper focuses on algorithmic construction and theoretical bounds rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Balanced Angle Splitting is Crucial: The core insight is that by splitting the angle range of a parent vertex among its children in proportion to their subtree sizes, the overall drawing area can be significantly reduced. This "balanced" approach prevents any single branch from dominating the drawing space.
  • Geometric Lemma for Grid Placement: Lemma 2.7 is a critical geometric tool that allows for precise placement of vertices on a grid while respecting the assigned angle ranges, which is fundamental to achieving the desired drawing properties.
  • "Gravity Root" Simplifies Unrooted Trees: Identifying a "gravity root" in unrooted trees (a vertex whose removal results in subtrees of balanced sizes) simplifies the problem by allowing a more controlled recursive decomposition, similar to the rooted case.
  • Convexity Achieved by Slope Inheritance: The paper shows that convex monotone drawings can be achieved by carefully managing slope inheritance between parent and child edges, ensuring that angles at vertices remain convex.

Key Results

  • $n \times n$ Grid for Rooted Trees: The primary result is an algorithm that produces a monotone drawing of a rooted ordered $n$-vertex tree within an $n \times n$ grid. This is a significant improvement over previous $12n \times 12n$ bounds.
  • Convex Monotone Drawings: The algorithm can be adapted to produce convex monotone drawings within the same $n \times n$ grid.
  • Efficient Unrooted Tree Drawings: For unrooted ordered trees, they achieve $(n+1) \times (n+1)$ grid drawings. For unrooted non-ordered trees, they achieve $\lceil \frac{n+2}{2} \rceil \times \lceil \frac{n+2}{2} \rceil$ grid drawings, offering good aspect ratios.
  • Theoretical Bounds: The paper provides rigorous proofs for the grid size bounds of their algorithms.

Limitations and Future Work

  • "Non-Ordered" Trees in Four-Quadrant Drawing: The four-quadrant algorithm explicitly states it does not respect the embedding of "non-ordered" trees, meaning the order of neighbors might be changed.
  • Open Problems: The authors pose two open problems:
  • Can the grid size bound of $\approx n \times n$ be improved further? Is there a tree that requires a larger grid?
  • What is the trade-off between angular resolution (how precisely angles can be represented) and grid size in monotone tree drawings?

Summary updated

Abstract

A monotone drawing of a graph G is a straight-line drawing of G such that every pair of vertices is connected by a path that is monotone with respect to some direction. Trees, as a special class of graphs, have been the focus of several papers and, recently, He and He [6] showed how to produce a monotone drawing of an arbitrary n-vertex tree that is contained in a $$12n \times 12n$$ grid. In this paper, we present a simple algorithm that constructs for each arbitrary tree a monotone drawing on a grid of size at most $$n \times n$$ .
BibTeX
@inproceedings{oikonomou2017simple,
  author = {Anargyros Oikonomou and Antonios Symvonis},
  title = {{Simple Compact Monotone Tree Drawings}},
  booktitle = {GD},
  year = {2017},
  url = {https://openreview.net/forum?id=07knxxX-_W},
}
Figure