How to Fit a Tree in a Box

Abstract

We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $\sqrt{n}$ by $\sqrt{n}$ grid. We also show that testing whether a given binary tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.

1 Introduction

Let $T = (V,E)$ be combinatorial tree; that is, a connected graph without cycles. A straight-line embedding of $T$ onto a grid is an injective map $f : V \rightarrow \mathbb {Z}^2$. An embedding is planar if for every pair of edges $(v_1,v_2), (w_1,w_2) \in E$ the line segments $f(v_1)f(v_2)$ and $f(w_1)f(w_2)$ do not intersect except at common endpoints. The size or dimensions of an embedding (or, with slight abuse of terminology, the size of the grid) is the width and height of the portion of $\mathbb {Z}^2$ used by $f$; that is,

$$ \dim _f (T) = \left( \max _{v \in V} x_{f(v)} - \min _{v \in V} x_{f(v)} + 1, \max _{v \in V} y_{f(v)} - \min _{v \in V} y_{f(v)} + 1 \right) . $$

We are interested in finding embeddings with as small a size as possible.

A rooted tree is a tree $T$ with a special vertex $r \in V$ marked as root. Because a tree has no cycles, a rooted tree has an induced partial order on its vertices: for two vertices $v, w \in V$, we say $v \prec w$ if and only if $v$ lies on the path from $r$ to $w$. An embedding is upward if, for all $v, w \in V$ with $v \prec w$, we have $y_{f(v)} > y_{f(w)}$. An embedding is weakly upward if, for all $v, w \in V$ with $v \prec w$, we have $y_{f(v)} \ge y_{f(w)}$.

Related Work. Drawing graphs with small area has a long and rich history [7]. By now, we are starting to have some understanding of when graphs admit drawings with linear area (a graph with $n$ nodes can be embedded on a $w \times h$ grid with $wh \in O(n)$), and when superlinear area is required. Chan [5] shows that every tree admits a drawing with $n2^{O(\sqrt{\log \log n \log \log \log n})}$ area, improving the long-standing $O(n \log n)$ bound one obtains by a simple divide-and-conquer layout algorithm.

However, not much is known about the exact minimum area requirements for graphs that do admit linear-area drawings. It is clear that not every tree admits a perfect drawing on a grid with exactly $n$ points: for instance, when the graph is a star, some grid points are “blocked” and cannot be used. The star graph can be drawn on a linear-area grid: Euler already showed that the fraction of points visible from the center of a square grid tends to $\frac{6}{\pi ^2}$ more than 300 years ago [8]. For graphs of bounded degree, there is hope that we can do better. Clearly, every path admits a perfect drawing. Garg and Rusu [9, 10] show that trees of degree $d = O(n^{\delta })$ with $\delta < 1/2$, and in particular of degree 3, have linear-area drawings onto a square grid, and even onto grids of different aspect ratio; their main concern is studying the relation between the aspect ratio and the area, but they do not give concrete bounds on the constant factor.

We conjecture that every degree $3$ tree admits a perfect drawing onto a square grid, and we prove here that this is the case for perfect binary trees.

When drawing rooted trees, a natural restriction is to require drawings to be upward. In this case, clearly, perfect drawings are impossible unless the tree is a path, but we may still investigate almost-perfect drawings that leave only few grid points unused. Chan [5] shows that for strictly upward drawings, we cannot do better than $\varTheta (n \log n)$ area. He does give an improved bound for weakly upward drawings.

Biedl and Mondal [4] proved NP-hardness for strictly upward unordered straight-line high-degree trees. Later, Biedl [3] gave an algorithm to find for every ternary tree $T$ a strictly upward order-preserving straight-line grid drawing of optimum width.

Contribution. We have the following results.

• It is NP-hard to test whether binary trees with fixed combinatorial embedding admit upward drawings on a given grid.

• Perfect binary trees with $n$ vertices admit drawings on a $\sqrt{n} \times \sqrt{n}$ grid.

2 Optimal Embeddings of Perfect Binary Trees

We consider the following setting. Given a $\sqrt{n} \times \sqrt{n}$ grid and a tree with $n$ vertices, can we draw it with straight non-crossing edges? Clearly this is not always possible, for instance if the tree is a star.

Conjecture 1

If the tree has max degree 3, it is always possible.

In particular, if $n=2^{k+1}$, a perfect binary tree of odd height $k$ with additional parent of the root (to make the number of vertices exactly $n$) can be drawn on the $\sqrt{n} \times \sqrt{n}$ grid. We use a recursive strategy to show it. Similar approaches recursively embedding trees have been previously used to show asymptotic bounds (but disregarding smaller order terms); in particular to prove that perfect binary trees and Fibonacci trees can be upward drawn in linear area [6] and to bound the area of complete ternary and 7-ary trees on the 8-grid [2].

Theorem 1

The perfect binary tree on $n=2^{k+1}-1$ vertices with $k$ odd can be embedded in the $\sqrt{n} \times \sqrt{n}$ square grid.

Proof

We will recursively argue that perfect binary trees can be embedded in square grids in two ways. Let $T_k$ be the perfect binary tree on $n=2^{k+1}-1$ vertices. We will recursively define two straight-line crossing-free drawings, $F_k$ and $G_k$, of $T_k$. The vertices in these drawings are placed in the grid points $\{(x,y) \in \mathbb {Z}^2:\ 1\le x \le 2^{(k+1)/2}, \ 1\le y \le 2^{(k+1)/2} \}$.

We first list the required properties of $F_k$ and $G_k$, also illustrated in Fig. 1a:

• (i) both $F_k$ and $G_k$ map the root of $T_k$ to the point $(2^{(k-1)/2} + 1, 2^{(k-1)/2})$;

• (ii) both $F_k$ and $G_k$ do not place any edges in the vertical strip between $x=2^{(k-1)/2}$ and $x=2^{(k-1)/2} + 1$, except for the edges incident to the root of $T_k$;

• (iii) $F_k$ leaves the point $(2^{(k-1)/2}, 1)$ unused; and

• (iv) $G_k$ leaves the point $(1, 1)$ unused.

Observe that $F_1 = G_1$ is trivial to draw: both are drawings of a path of length $2$, drawn by connecting the point $(1,2)$ to the point $(2,1)$ to the point $(2,2)$.

What remains is to argue that we can recursively draw $F_k$ and $G_k$ using drawings of $F_{k-2}$ and $G_{k-2}$. The argument is illustrated in Fig. 1; the detailed proof can be found in the full version [1].    $\square$

Fig. 1.

Recursive embedding of perfect binary trees.

3 Upward Embedding of Trees in a Given Grid is NP-Hard

Recall that an embedding of a rooted tree is upward if the $y$-coordinate of a node is strictly greater than the $y$-coordinate of its children. A combinatorial embedding is given by a circular order of incident edges around each vertex. In this section we show that deciding if a rooted binary tree with a fixed combinatorial embedding can be drawn upward and without crossings in a given square grid is NP-complete.

Theorem 2

Deciding whether an upward planar straight-line drawing of a fixed combinatorial embedding of a rooted binary tree on a grid of given size $(w \times h)$ exists is NP-complete.

Fig. 2.

Reduction from 3-SAT. (Color figure online)

Proof

The problem is in NP since a geometric drawing of a tree with $k$ vertices in the grid can be expressed in $O(k)$ size by assigning vertices to grid points. Checking whether the drawing is an embedding can trivially be done in $O(k^2)$ time by checking pairwise edge crossings. Checking whether the drawing preserves the given rotation system takes $O(k^2)$ time and checking whether it is upward can be done in $O(k)$ time.

We prove NP-hardness by a reduction from 3SAT which is an NP-complete problem [11]. An instance of 3SAT is given by a set $\{x_1,\ldots ,x_n\}$ of $n$ variables and a set $\{c_1,\ldots ,c_m\}$ of $m$ clauses. Each variable can assume one of two values in $\{\texttt {true}, \texttt {false}\}$. Each clause is defined by 3 literals, i.e., positive or negative copies of a variable. A clause is satisfied if at least one of its literals is true. The problem 3SAT asks for an assignment from the variables to $\{\texttt {true}, \texttt {false}\}$ that satisfies all clauses. We give an arbitrary order for the variables and say that $x_i$ appears before $x_j$ if $i<j$. The first (resp., second, resp., third) literal of a clause is the literal (among the 3 literal that define the clause) of the variable that appears first (resp., second, resp., third) in the order assigned to variables. Given an instance of 3SAT we build a rooted tree with $O(m^2+mn)$ vertices and set $w=4m+4$ and $h=\lceil \lg (4m+4)\rceil +5n+4m+1$.

Overview. Refer to Fig. 2. This paragraph gives a brief informal overview of the reduction. The following paragraphs will give a full proof. The reduction is divided into 3 parts. The top part (spanning the top $\lceil \lg (4m+4)\rceil$ rows in Fig. 2) is a perfect binary tree with $2^{\lceil \lg (4m+4)\rceil -1}$ leaves. The middle part (spanning the next $5n$ rows in Fig. 2) is where the variables are assigned a boolean value. The bottom part (spanning the last $4m+1$ rows in Fig. 2) enforces that every clause of the original instance of 3SAT is satisfied. Each variable is represented by a red subtree with two long paths that have to span all but one row below the least common ancestor. The left (resp., right) path represents a positive (resp., negative) literal of the variable. The construction forces one of the paths to be drawn one unit above the other and that encodes the boolean assignment. If the left path does not span the last row, then the variable is set to true. The variable is set to false otherwise. In Fig. 2, $x_2$ and $x_3$ (resp., $x_1$ and $x_4$) are set to true (resp., false). The blue subtrees encode the clauses by allowing the rest of the construction to occupy specific extra grid positions. The incidence of a variable in a clause is encoded by an extra leaf child in one of the paths that represent the incident literal corresponding to the variable. If none of the incident literals of a clause are set to true, the drawing would require the use of an extra row or column. Otherwise, the extra leaves can be accommodated exactly by the space provided by the blue subtrees.

Construction. There are exactly $4m+4$ subtrees attached to the perfect binary tree on the top of the construction. The fixed combinatorial embedding prescribes a left-to-right order of such subtrees. For each variable $x_i$, do the following. Set the $4(i-1)+1$-th subtree to be a path $p$ of length $5n+4m$; attach another path of length $5n+4m-5(i-1)-4$ to the right of the $5(i-1)+4$-th vertex of $p$. Attach a right child to the second to last vertex of $p$. Set the $4(i-1)+2$-th subtree to be a path of length $5(i-1)+1$. Set the $4(i-1)+3$-th subtree to be a path of length $5(i-1)$. At the end of the path, attach two paths $p_t$ and $p_f$ of length $5(n-i+1)+4m-2$ each as left and right subtrees respectively. Attach a right (resp., left) child to the first vertex of $p_t$ (resp., $p_f$). We now describe the position of the vertices that encode the incidence of a variable in a clause. We call such vertices literal leaves. If $x_i$ (resp., $\overline{x_i}$) is the first or second literal of $c_j$, then add a right child $\ell _{i,j}$ to the $5(n-i+1)+4(m-1)$-th vertex of $p_t$ (resp., $p_f$). If $x_i$ (resp., $\overline{x_i}$) is the third literal of $c_j$, then add a left child $\ell _{i,j}$ to the $5(n-i+1)+4(m-1)$-th vertex of $p_t$ (resp., $p_f$). The $4(i-1)+3$-th subtree is shown in red in Fig. 2. Set the $4(i-1)+4$-th subtree to be a path of length $5(i-1)$. Finally, we describe the four last subtrees (shown in blue in Fig. 2). Set the $4m+1$-th, $4m+2$-th, and $4m+3$-th subtrees to be paths of length $5n+4m$ each. For every clause $c_j$, attach a right leaf child to the $5n+4j$-th vertex of the $4m+3$-th subtree. Set the last subtree to be a path of length $5n$. For each variable $x_i$, attach a right leaf child to the $5i-4$-th vertex of the path. This finalizes the construction.

Correctness. We argue that the construction is correct, by showing that every satisfiable 3SAT instance can indeed be embedded in a $w \times h$ grid, and that every drawing that fits in a $w \times h$ grid must correspond to a satisfiable 3SAT instance. The details can be found in the full version [1].    $\square$

4 Conclusions

We studied tree drawings in small areas.

For arbitrary drawings, we gave a construction for embedding a perfect binary tree on a square grid. The main remaining open question here is whether every low-degree tree with $wh$ vertices (or fewer) can be embedded on an $w \times h$ grid. We conjecture that this is the case when $w=h$. Another intriguing question is whether, for general trees, testing if they can be embedded on a given grid is computationally tractable.

For upward drawings, we showed that even for bounded-degree trees, testing whether a given tree can be embedded in a $w \times h$ rectangle is already NP-hard, if the combinatorial embedding of the tree is fixed. It would be interesting to know whether the same is true when one can freely choose the combinatorial embedding. Another question is whether the problem is also NP-hard for weakly upward drawings, where adjacent vertices may be embedded using the same $y$-coordinate.