# Generalized LR-drawings of trees

Therese Biedl David R. Cheriton School of Computer Science, University of
Waterloo, Canada<EMAIL_ADDRESS>Giuseppe Liotta Department
of Engineering, University of Perugia, Italy
<EMAIL_ADDRESS>Jayson Lynch
-1-1footnotemark: -1 Fabrizio Montecchiani00footnotemark: 0

###### Abstract

The LR-drawing-method is a method of drawing an ordered rooted binary tree
based on drawing one root-to-leaf path on a vertical line and attaching
recursively obtained drawings of the subtrees on the left and right. In this
paper, we study how to generalize this drawing-method to trees of higher
arity. We first prove that (with some careful modifications) the proof of
existence of a special root-to-leaf path transfers to trees of higher arity.
Then we use such paths to obtain _generalized_ LR-drawings of trees of
arbitrary arity.

##  1 Introduction

Tree-drawing is a very popular topic in the graph drawing literature. Nearly
all tree-drawing methods required that the drawing is planar (has no
crossing), but there are many other variations, depending on whether we demand
that the drawing is straight-line (as opposed to permitting bends in edges)
and/or order-preserving (a given order of edges at each node is maintained).
For a rooted tree, one also distinguishes by whether the drawing must be
(strictly) upward (nodes are (strictly) above their descendants). In all our
drawings, we assume that nodes (and also bends, if there are any) are placed
at grid-points, i.e., points with integer coordinates. The main objective is
to obtain drawings of small area, measured via the number of grid-points in
the minimum enclosing bounding box of the drawing. Sometimes one also
considers the width and height of the drawing, measured by the number of
columns (respectively rows) that intersect the drawing. We refer to a survey
by Di Battista and Frati [6] for many results up to 2014, and to Chan’s recent
paper [3] for some development since.

In 2002, Chan [2] published a tree-drawing paper that became the inspiration
for many follow-up papers. In particular, he studied rooted trees and only
considered ideal drawings, i.e., drawings that respect all four of the above
constraints (planar, straight-line, order-preserving and strictly upward). His
area-results were superseded by later improvements [9, 1, 3], but the
techniques introduced in [2] are still widely useful; see e.g. a recent paper
by Frati, Patrignani and Roselli [8] that uses Chan’s recursive approaches to
obtain small straight-line drawings of outer-planar graphs.

#### Background and related results.

One of the methods proposed by Chan [2] is the one that creates LR-drawings.
The idea is to take a root-to-leaf path $\pi$, drawing it vertically, and
attach the left and right subtrees of the path just below their parent, using
a recursively obtained drawing for the subtree. See Figure 1, where the nodes
of $\pi$ are white (as in all other figures). These drawings are defined only
for binary trees.

To describe this precisely, we need a few definitions. Let $T$ be a rooted
binary tree that comes with a fixed order of children at each node (we call
this an ordered rooted binary tree). A root-to-leaf path $\pi=\langle
v_{1},v_{2},\dots,v_{\ell}\rangle$ is a path in $T$ where $v_{1}$ is the root
and $v_{\ell}$ is a leaf. A left subtree of a path $\pi$ is a subtree rooted
at some child $c$ of a vertex $v_{i}\in\pi$ for which $c$ comes before the
path-child in the order at $v_{i}$. We call this a left subtree at $v_{i}$
when needing to specify the node of $\pi$. A right subtree is defined
symmetrically.

The LR-drawing-method consists of picking a root-to-leaf path $\pi$, drawing
it vertically, and attaching (recursively obtained) drawings of the subtrees
of $T\setminus V(\pi)$ on the left and right side so that the order is
maintained. Since $T$ is binary, there is only one such subtree at each
$v\in\pi$; we place its drawing in the rows just below $v$ (after lengthening
edges of $\pi$ as needed) and one unit to the left/right of path $\pi$.

Figure 1: An LR-drawing where $\pi=\langle v_{1},v_{2},\ldots v_{\ell}\rangle$
and $L_{i}$ and $R_{i}$ are various subtrees.

Let $W(n)$ be the maximum (over all binary trees $T$ with $n$ nodes) of the
width of the drawing, and note that it observes the following recursion:

$W(n)\leq
1+\min_{\pi}\left(\max_{\alpha}W(|\alpha|)+\max_{\beta}W(|\beta|)\right)$ (1)

where $\alpha$ and $\beta$ are the maximum left and right subtree,
respectively. We are therefore interested in picking a path $\pi$ that has
useful bounds on the size of $\alpha$ and $\beta$. Chan showed that there
exists a path such that $|\alpha|+|\beta|\leq n/2$, for any left and right
subtrees $\alpha$ and $\beta$. He then improved this to the following:

######  Lemma 1.

[2] Let $p=0.48$. Given any binary ordered rooted tree $T$ of size $n$, there
exists a root-to-leaf path $\pi$ such that for any left subtree $\alpha$ and
any right subtree $\beta$ of $\pi$,
$|\alpha|^{p}+|\beta|^{p}\leq(1-\delta)n^{p}$ for some constant $\delta>0$.

Lemma 1, together with Equation 1, and an inductive argument, implies the
existence of LR-drawings of width $O(n^{0.48})$ (and the height is $n$, as it
is for all LR-drawings constructed as described above). Later on, Frati et al.
[8] showed that for some binary trees, a width of $\Omega(n^{0.418})$ is
required in any LR-drawing, and this was improved further to
$\Omega(n^{0.429})$ by Chan and Huang [4]. The latter paper also gave another
construction-method that does not follow the above method exactly, instead the
chosen path $\pi$ may have some non-vertical edges while some left or right
subtree of $\pi$ complete the vertically drawn path. In this way, they can
obtain drawings of width $O(n^{0.437})$.

As should be clear from the above lower bounds, LR-drawings are not the best
tool for small-area ideal tree-drawings, since other papers can achieve width
$O(\log n)$ (or better if the pathwidth is small) [1, 9] while keeping the
height at $n$. But LR-drawings have a number of other appealing features:

  * •

Drawings of disjoint rooted subtrees are “vertically separated”, i.e., if
$T_{v}$ and $T_{w}$ are two disjoint rooted subtrees, then there exists some
horizontal line that separates the drawings of $T_{v}$ and $T_{w}$. (This can
be seen by studying the construction at the lowest common ancestor of the two
trees.) As such, the drawings are perhaps easier to understand than drawings
created with other methods (such as [9]) that delay the drawing of a subtree
until further down, leading to ‘interleaved’ drawings of subtrees.

  * •

LR-drawings (and in particular Lemma 1) has been used for a number of graph
drawing results, including for octagonal drawings, orthogonal drawings, and
drawings of outer-planar graphs [5, 7, 10].

  * •

Last but not least, “the question on LR-drawings is still interesting and
natural, as it is fundamentally about combinatorics of trees, or more
specifically, decompositions of trees via path separators” [4].

#### Contribution.

Our interest in LR-drawings originally came from the need to generalize Lemma
1 to rooted trees with higher arity, i.e., maximum number of children at a
node. (As we will detail in a separate, forthcoming, paper, such a lemma for
ternary trees can be used to obtain drawings of outer-1-planar graphs with
smaller area.) In the process, we discovered that all the results and
applications of LR-drawings seem to be only concerned with binary trees. It is
not even clear what exactly an LR-drawing should be for trees of higher arity,
and no area-bounds are known. Our results in this paper are as follows:

  * •

We first show (in Lemma 2 in Section 2) that Lemma 1 holds for trees of
arbitrary arity.

There does not seem to be an easy way to derive this result from Chan’s
result, since it is not clear how we could modify a rooted tree $T$ into a
binary tree without either increasing the number of nodes or missing a subtree
that may be too big. For this reason, we re-prove the result from scratch. The
proof is similar in structure to the one by Chan, but we need to be much more
careful in defining the inequalities that hold if we can extend the path to a
subtree.

  * •

We then discuss in Section 3 what the appropriate generalization of LR-
drawings to trees of higher arity should be. We also give a simple
construction that shows that ideal LR-drawings of area $O(n^{2})$ always
exist.

  * •

In Section 3.1 and 3.2, we then give constructions for generalized LR-drawings
that are directly based on Lemma 2 and therefore achieve $O(n^{0.48})$ width.
Unfortunately, neither construction gives ideal drawings: the first one has
one bend per edge, and the second one is not upward. Both constructions can be
modified to achieve ideal drawings, but at the expense of increasing the
height (possibly more than polynomially).

  * •

In Section 3.3, we give a construction for generalized LR-drawings that are
ideal drawings. The price to pay is that the construction is more complicated,
and the height (which was linear in the previous constructions) increases to
$O(n^{1.48})$, meaning that the area is only just barely sub-quadratic, namely
$O(n^{1.96})$.

We end in Section 4 with open questions.

##  2 Choosing a path

In this section, we show that Lemma 1 can be generalized to any ordered rooted
tree, regardless of its arity.

######  Lemma 2.

Let $p=0.48$. Given any ordered rooted tree $T$ of size $n$, there exists a
root-to-leaf path $\pi$ in $T$ such that for any left subtree $\alpha$ and any
right subtree $\beta$ of $\pi$, $|\alpha|^{p}+|\beta|^{p}\leq(1-\delta)n^{p}$
for some constant $\delta>0$.

###### Proof.

We will iteratively expand path $\pi=\langle v_{1},\dots,v_{i}\rangle$ to get
closer to a leaf, and let $\alpha_{i},\beta_{i}$ be the largest left/right
subtree of this path (not considering the subtrees at $v_{i}$). Initially set
$v_{1}$ to be the root. We maintain the invariant that
$|\alpha_{i}|^{p}+|\beta_{i}|^{p}\leq(1-\delta)n^{p}$ for every $i$; this
holds vacuously initially.

Now assume that path $\pi$ up to $v_{i}$ for some $i\geq 0$ has been chosen.
Let $S_{i}^{(1)},\dots,S_{i}^{(d_{i})}$ be the subtrees at $v_{i}$, enumerated
from left to right. Call such a subtree $S_{i}^{(k)}$ feasible if we could use
its root to extend $\pi$. Thus $S_{i}^{(k)}$ is feasible if

$\displaystyle\max\left\\{|\alpha_{i}|,|S_{i}^{(1)}|,\dots,|S_{i}^{(k-1)}|\right\\}^{p}$
$\displaystyle+\max\left\\{|\beta_{i}|,|S_{i}^{(k+1)}|,\dots,|S_{i}^{(d_{i})}|\right\\}^{p}$
$\displaystyle\leq$ $\displaystyle(1-\delta)n^{p}.$

For future reference we note that $S_{i}^{(k)}$ is infeasible if one of the
following three violations occurs:

  1. 1.

$|\alpha_{i}|^{p}+|S_{i}^{(\ell)}|^{p}>(1-\delta)n^{p}$ for some $\ell>k$.

  2. 2.

$|S_{i}^{(h)}|^{p}+|\beta_{i}|^{p}>(1-\delta)n^{p}$ for some $h<k$.

  3. 3.

$|S_{i}^{(h)}|^{p}+|S_{i}^{(\ell)}|^{p}>(1-\delta)n^{p}$ for some $h<k<\ell$.

Case 1: Exactly one subtree $S_{i}^{(k)}$ is feasible. Then we set $v_{i+1}$
to be the root of $S_{i}^{(k)}$. The invariant holds by choice of “feasible”.

Case 2: At least two subtrees $S_{i}^{(k)}$, $S_{i}^{(\ell)}$ (with $k<\ell$)
are feasible. We terminate the construction as follows.

Consider first the subcase where $|S_{i}^{(k)}|\leq|S_{i}^{(\ell)}|$. Set path
$\pi$ to be the concatenation of $\langle v_{1},\dots,v_{i}\rangle$ with the
leftmost path in $S_{i}^{(k)}$ down to a leaf. A left subtree of this path has
size at most $\max\\{|\alpha_{i}|,\max_{h<k}|S_{i}^{(h)}|\\}$. A right subtree
of this path up to $v_{i}$ has size at most
$\max\\{|\beta_{i}|,\max_{h>k}|S_{i}^{(h)}|\\}$. A right subtree of this path
below $v_{i}$ is a subtree of $S_{i}^{(k)}$ (and hence no bigger than
$|S_{i}^{(k)}|\leq|S_{i}^{(\ell)}|\leq\max_{h>k}|S_{i}^{(h)}|$ by assumption).
Since $S_{i}^{(k)}$ is feasible the invariant holds.

The other subcase, $|S_{i}^{(\ell)}|\leq|S_{i}^{(k)}|$ can be handled in a
symmetric fashion by extending instead with the rightmost path in
$S_{i}^{(\ell)}$.

######  Claim 1.

One of the above two cases always applies.

###### Proof.

Assume not. To show that this leads to a contradiction, we find some subtrees
(or collections of subtrees) for which we can lower-bound the size. This part
is significantly more complicated than in Chan’s proof because there are now
multiple ways in which a subtree might not be feasible, and we must choose our
subtrees correspondingly. Consider Figure 2 for an illustration of the
following definitions.

Figure 2: The situation up to symmetry.

Suppose that the parent of $\beta_{i}$’s root, which we denote by $v_{j}$, is
no higher than the parent of $\alpha_{i}$’s root; the other case is symmetric.
We first derive one inequality from $v_{j}$. We have $j<i$ by definition of
$\beta_{i}$. Because we did not terminate the path when extending at $v_{j}$,
Case 2 did not apply at $v_{j}$. Therefore the subtree $S_{j}^{(k)}$ of
$v_{j}$ that contains $v_{i}$ was the only feasible subtree at $v_{j}$.

Consider Figure 3. Tree $\beta_{i}$ is a right subtree at $v_{j}$, say it was
$S_{j}^{(\ell)}$ with $\ell>k$. Let $\mathcal{L}_{j}$ be the collection of
subtrees $S_{j}^{(1)},\dots,S_{j}^{(\ell-1)}$. We know that $S_{j}^{(\ell)}$
was infeasible, and study the three possible violations:
(1) $|\alpha_{j}|^{p}+|S_{j}^{(\ell^{\prime})}|^{p}>(1-\delta)n^{p}$ for some
$\ell^{\prime}>\ell$. But this is impossible since $S_{j}^{(k)}$ is feasible
and $k<\ell$.
(2) $|S_{j}^{(k^{\prime})}|^{p}+|\beta_{j}|^{p}>(1-\delta)n^{p}$ for some
$k^{\prime}<\ell$ (possibly $k=k^{\prime}$). In this case, set
$B_{j}:=\beta_{j}$.
(3) $|S_{j}^{(k^{\prime})}|^{p}+|S_{j}^{(\ell^{\prime})}|^{p}>(1-\delta)n^{p}$
for some $k^{\prime}<\ell<\ell^{\prime}$. In this case, set
$B_{j}:=S_{j}^{(\ell^{\prime})}$. Note that either way $B_{j}$ is disjoint
from $\beta_{i}=S_{j}^{(\ell)}$ and a right subtree of one of
$v_{1},\dots,v_{j}$, so also disjoint from $\mathcal{L}_{j}$. Subtree
$S_{j}^{(k^{\prime})}$ that caused the above violation for $S_{j}^{(\ell)}$
belongs to $\mathcal{L}_{j}$, and therefore

$|\mathcal{L}_{j}|^{p}+|B_{j}|^{p}>(1-\delta)n^{p}$ (2)

Figure 3: Close-up on $v_{j}$. Red arrows indicates pairs of subtrees that
violate feasibility.

Now we define two subtrees $L_{i},R_{i}$ at $v_{i}$. Since the leftmost
subtree $S_{i}^{(1)}$ at $v_{i}$ is infeasible, but extending into it would
not add left subtrees to the path, the infeasibility must be caused by
violation (1), i.e., there exists some $k>1$ such that
$|S_{i}^{(k)}|^{p}+|\alpha_{i}|^{p}>(1-\delta)n^{p}$. Set $R_{i}$ to be this
subtree $S_{i}^{(k)}$, choosing the largest possible index $k$. We have

$|R_{i}|^{p}+|\alpha_{i}|^{p}>(1-\delta)n^{p}.$ (3)

Symmetrically, since the rightmost subtree $S_{i}^{(d_{i})}$ at $v_{i}$ is
infeasible, there must be some $h<d_{i}$ such that
$|S_{i}^{(h)}|^{p}+|\beta_{i}|^{p}>(1-\delta)n^{p}$. Set $L_{i}$ to be this
subtree $S_{i}^{(h)}$, choosing the smallest possible index $h$. We have

$|L_{i}|^{p}+|\beta_{i}|^{p}>(1-\delta)n^{p}.$ (4)

Note that it is possible $L_{i}=R_{i}$ and that both are subsets of
$\mathcal{L}_{j}$.

Case A: $L_{i}\neq R_{i}$. See Figure 4. In this case the contradiction is
obtained exactly as done by Chan, except by substituting the trees/forests
that we have chosen above suitably. Recall that Hölder’s inequality states
that for $p<1$ we have

$\sum_{a}x_{a}y_{a}\leq\left(\sum x_{a}^{1/(1-p)}\right)^{1-p}\left(\sum
y_{a}^{1/p}\right)^{p}$

(in some of our applications below we use $x_{a}\equiv 1$). We can derive a
contradiction for the value $p=0.48$ (with a sufficiently small $\delta$) by
combining Equations (2-4) as follows:

$\displaystyle 2.5(1-\delta)n^{p}$ $\displaystyle<$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+|L_{i}|^{p}+|R_{i}|^{p}+0.5|\mathcal{L}_{j}|^{p}+0.5|B_{j}|^{p}$
$\displaystyle\leq$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+2^{1-p}(|L_{i}|+|R_{i}|)^{p}+0.5|\mathcal{L}_{j}|^{p}+0.5|B_{j}|^{p}$
$\displaystyle\leq$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+(2^{1-p}+0.5)|\mathcal{L}_{j}|^{p}+0.5|B_{j}|^{p}$
$\displaystyle\leq$
$\displaystyle\left(1+1+(2^{1-p}+0.5)^{1/(1-p)}+0.5^{1/(1-p)}\right)^{1-p}$
$\displaystyle\quad\quad\quad\quad\cdot(|\alpha_{i}|+|\beta_{i}|+|\mathcal{L}_{j}|+|B_{j}|)^{p}$
$\displaystyle<$ $\displaystyle 2.499n^{p}$

since $\alpha_{i},\beta_{i},\mathcal{L}_{i}$ and $B_{j}$ are all disjoint.

Figure 4: Close-up on $v_{i}$, Case (A).

Case B: $L_{i}=R_{i}$. In this case we derive one further inequality, see
Figure 5. Since $R_{i}=S_{i}^{(k)}$ is not feasible, there must exist a
violation, and we consider its three possible forms. (1)
$|S_{i}^{(\ell)}|^{p}+|\alpha_{i}|^{p}>(1-\delta)n^{p}$ for some $\ell>k$. But
this is impossible since $R_{i}$ was chosen as the rightmost such violation.
(2) $|S_{i}^{(h)}|^{p}+|\beta_{i}|^{p}>(1-\delta)n^{p}$ for some $h<k$. But
this is impossible since $R_{i}=L_{i}$ was chosen as the leftmost such
violation. (3) $|S_{i}^{(h)}|^{p}+|S_{i}^{(\ell)}|^{p}>(1-\delta)n^{p}$ for
some $h<k<\ell$. In this case we define $\hat{L}_{i}:=S_{i}^{(h)}$ and
$\hat{R}_{i}:=S_{i}^{(\ell)}$. Summarizing, $\mathcal{L}_{j}$ contains the
three mutually distinct subtrees $\hat{L}_{i},L_{i}{=}R_{i},\hat{R}_{i}$ and

$|\hat{L}_{i}|^{p}+|\hat{R}_{i}|^{p}>(1-\delta)n^{p}$ (5)

Figure 5: Close-up on $v_{i}$, Case (B).

Using again Hölder’s inequality we obtain the desired contradiction: by
combining Equations(2-5) (and $L_{i}=R_{i}$) as follows:

$\displaystyle 3.5(1-\delta)n^{p}$ $\displaystyle<$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+2|R_{i}|^{p}+|\hat{L}_{i}|^{p}+|\hat{R}_{i}|^{p}$
$\displaystyle\quad\quad+0.5|\mathcal{L}_{j}|^{p}+0.5|B_{j}|^{p}$
$\displaystyle\leq$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+(2^{1/(1-p)}+2)^{1-p}(|R_{i}|+|\hat{L}_{i}|+|\hat{R}_{i}|)^{p}$
$\displaystyle\quad\quad+0.5|\mathcal{L}_{j}|^{p}+0.5|B_{j}|^{p}$
$\displaystyle\leq$
$\displaystyle|\alpha_{i}|^{p}+|\beta_{i}|^{p}+((2^{1/(1-p)}+2)^{1-p}+0.5)|\mathcal{L}_{j}|^{p}$
$\displaystyle\quad\quad+0.5|B_{j}|^{p}$ $\displaystyle\leq$
$\displaystyle(1+1+((2^{1/(1-p)}+2)^{1-p}+0.5)^{1/(1-p)}$
$\displaystyle\quad\quad+0.5^{1/(1-p)})^{1-p}\cdot\left(|\alpha_{i}|+|\beta_{i}|+|\mathcal{L}_{j}|+|B_{j}|\right)^{p}$
$\displaystyle<$ $\displaystyle 3.396n^{p}.$

So the claim holds. ∎

So one of Case 1 or Case 2 always applies, and we can continue to expand the
path until we terminate it in some application of Case 2. ∎

##  3 Generalized LR-drawings

LR-drawings for binary trees were defined via two particular construction
operations. In contrast, we want to define here generalized LR-drawings via
the properties that the drawings must satisfy. Let $T$ be an ordered rooted
tree, and consider an order-preserving planar drawing $\Gamma$ of $T$. We call
$\Gamma$ a generalized LR-drawing (or GLR-drawing for short) if it (and all
induced drawings of rooted subtrees) satisfies the following two conditions:

  1. (P1)

(vertical path): There exists a root-to-leaf path $\pi$ $\langle
v_{1},\dots,v_{\ell}\rangle$ that is drawn vertically aligned, with $v_{i}$
above $v_{i+1}$ for $1\leq 1<\ell$.

  2. (P2)

(path-separation): The column that contains $\pi$ separates the drawings of
the left and right subtrees, i.e., for any left or right subtree $T^{\prime}$,
the drawing $\Gamma^{\prime}$ of $T^{\prime}$ induced by $\Gamma$ does not use
the column containing $\pi$.

Clearly any LR-drawing for binary trees satisfies these two conditions, so
this is indeed a generalization. As one can verify by inspecting the proofs,
these are the only two conditions needed for the lower-bound arguments in [8]
and [4]. We hence have:

######  Corollary 1 (based on [4]).

For every positive $n$ there exists an $n$-node ordered rooted tree $T$ such
that any GLR-drawing of $T$ has width $\Omega(n^{0.429})$.

We note that many existing algorithms for ideal drawings of trees (see e.g.
[1, 2, 9]) satisfy the condition on drawing some path $\pi$ vertically. The
real restriction on GLR-drawings is that the vertical path separates the left
and right subtrees. The algorithms in [1,2,9] all reuse the column of the
vertically-drawn path for some large subtree that has been “pushed down”.

There are many more properties that are satisfied by the LR-drawings for
binary trees (and so arguably one could have included them in the definition
of GLR-drawings, though for maximal flexibility we chose not to do that). All
LR-drawings of binary trees, and also all drawings that we will create,
satisfy the following three properties:

  1. (P3)

(horizontal separation of subtrees). For any node $v$ of $T$, let $T_{v}$ be
the subtree rooted at $v$. There exists a horizontal strip that contains all
nodes of $T_{v}$ and that does not contain any other node of $\Gamma$.

  2. (P4)

(grouping of subtrees at $v_{i}$). For any node $v_{i}\in\pi$, there exists a
horizontal strip that contains $v_{i}$ and all nodes of all left and right
subtrees at $v_{i}$ and that does not contain any other node of $\Gamma$.

inline]TB: Jayson had convinced me once that P3 implies P4, but now I no
longer believe it. To be on the safe side, I removed that comment. jl: I don’t
object to leaving that statement out. I think it follows because $v_{i-1}$ is
not in the subtree of $v_{i}$ and thus can’t be in the same band. $v_{i+1}$ is
not in the subtree rooted at the other children of $v_{i}$ so we shouldn’t be
able to go downwards either. TB: But some subtree at $v_{i}$ could “reach
down” with a long edge and be drawn below $v_{i+1}$ and its subtrees. (It
would look roughly like Fig. 10 (right) except that there is $v_{i+1}$ and
some subtree in the bottom left quadrant of $R$.) Then P3 holds but P4
doesn’t.

  3. (P5)

(grouping of left/right subtrees at $v_{i}$). For any node $v_{i}\in\pi$,
there exists a horizontal strip that contains all nodes of all left subtrees
at $v_{i}$ and does not contain any other nodes of $\Gamma$. There also exists
a horizontal strip that contains all nodes of all right subtrees at $v_{i}$
and does not contain any other nodes of $\Gamma$.

Finally, there are three more properties that the LR-drawings of binary trees
satisfy, but some of our constructions do not (and as we will argue, we cannot
hope to satisfy them and have sub-quadratic area).

  1. (P6)

The drawing is straight-line.

  2. (P7)

The drawing is strictly upward.

  3. (P8)

(minimum-distance) Bounding boxes of subtree-drawings have the minimum
possible distance to the path and to each other.

Formally, we use $B(T^{\prime})$ to denote the bounding box of the drawing of
rooted subtree $T^{\prime}$. We require that if $T^{\prime}$ is a left subtree
of $\pi$, then the right side of $B(T^{\prime})$ lies one unit left of $\pi$,
and symmetrically for right subtrees. We also require minimal vertical
distances between bounding boxes, most easily expressed by demanding that
every row contains a node.

inline]TB: It occurred to me that we should split P8 into two conditions, one
about distances in $x$-direction and one about distances in $y$-direction
(call the latter P9).
For example, the 1-bend construction satisfies the former, but not P9. Also,
any drawing that satisfies the P8 has width $O(n^{0.48})$ if we use $\pi$ from
Lemma 2, and any drawing that satisfies P9 has height $n$. It might be worth
stating that.
I don’t want to do such a major change for the CCCG submission this late in
the game, but let’s do this for the revision (assuming it gets accepted).

We first show that all eight conditions given above can be satisfied
simultaneously if we allow for quadratic area. The construction is the
“standard construction” [3] and hence nearly trivial; we repeat the details
for completeness’ sake.

######  Lemma 3.

Any $n$-node ordered rooted tree has a GLR-drawing that additionally satisfies
conditions (P3)-(P8) and has area $O(n^{2})$. Furthermore, the root is placed
in the top-left corner of the bounding box.

###### Proof.

If $T$ consists of a single node, draw such node as an arbitrary point in the
plane. Otherwise let $R^{(1)},\dots,R^{(d)}$ be the subtrees rooted at the
children of the root $v_{T}$ of $T$, enumerated from _right to left_.
Recursively compute a drawing for each such subtree and combine them as
follows. The drawing of $R^{(1)}$ is placed such that the top side of its
bounding box $B(R^{(1)})$ is one unit below $v_{T}$, while its left side is
one unit to the right of $v_{T}$. The drawing of $R^{(i)}$, $1<i<d$, is placed
such that the top side of $B(R^{(i)})$ is one unit below the bottom side of
$B(R^{(i-1)})$, while its left side is again one unit to the right of $v_{T}$.
The drawing of $R^{(d)}$ is drawn such that its root is vertically aligned
with $v_{T}$ and the top side of $B(R^{(d)})$ is one unit below the bottom
side of $B(R^{(d-1)})$. (This corresponds to choosing $\pi$ as the leftmost
path of $T$.) It is easy to verify that each edge can be drawn as a straight-
line segment, and that the resulting drawing is a strictly-upward GLR-drawing
that satisfies all conditions. Moreover, the construction guarantees that both
the width and the height are at most $n$. ∎

Figure 6: Construction an ideal GLR-drawing of a $d$-ary tree in $O(n^{2})$
area.

Unfortunately, it turns out that we cannot hope for smaller area if we want to
satisfy all conditions.

######  Lemma 4.

For every positive integer $k$ there exists an ordered rooted tree $T$ with
$n=6k-1$ nodes and arity 4 such that any GLR-drawing of $T$ that also
satisfies conditions (P3)-(P8) for all subtrees has area $\Omega(n^{2})$.

###### Proof.

Tree $T$ consists of root $r$ with four children
$\ell,v_{1},v_{1}^{\prime},\ell^{\prime}$, where $\ell,\ell^{\prime}$ are
leaves while $v_{1}$ and $v_{1}^{\prime}$ are each roots of trees of height
$k$. Specifically, for $1\leq i<k$, nodes $v_{i}$ and $v_{i}^{\prime}$ each
have three children: one leaf, node $v_{i+1}$ resp. $v_{i+1}^{\prime}$, and
another leaf. See Figure 7 for the case when $k=4$.

Figure 7: Construction of a family of trees that require quadratic area in any
GLR-drawing that satisfies all conditions (P3)-(P8).

Fix an arbitrary GLR-drawing of $T$ that satisfies criteria (P3)-(P8). Up to
symmetry, we may assume that the vertically drawn path $\pi$ uses
$v_{1}^{\prime}$ or $\ell^{\prime}$, so $\ell$ and $T_{v_{1}}$ are both left
subtrees. By the minimum-distance condition, and since $T_{\ell}$ only
consists of $\ell$, the location of $\ell$ is one unit left of path $\pi$. (It
may be one or two units below $r$, depending on the location of
$\ell^{\prime}$, but our proof will not use this.) Now consider the bounding
box $B(T_{v_{1}})$ of the drawing of $T_{v_{1}}$. Again by the minimum-
distance condition, its right side must be one unit left of path $\pi$. Since
left subtrees at root $r$ are grouped, distances are minimum and the drawing
is ordered, the top side of $B(T_{v_{1}})$ must be one unit below $\ell$.
Since the drawing is strictly-upward, node $v_{1}$ is in the top row of
$B(T_{v_{1}})$. Since $(r,v_{1})$ is drawn with a straight-line segment, this
requires $v_{1}$ to be on the top right corner of $B(T_{v_{1}})$, otherwise
the drawing would not be order-preserving at $r$ or $(r,v_{1})$ would overlap
$\ell$.

So we now know that $T_{v_{1}}$ is drawn with its root in the top right
corner. It follows that the path $\pi^{\prime}$ used for drawing $T_{v_{1}}$
must use the right child of $v_{1}$, i.e., goes to a leaf while $T_{v_{2}}$ is
a left subtree of $\pi^{\prime}$. But notice that now the situation is
repeated: at $v_{1}$, there exists a leaf, then the subtree $T_{v_{2}}$, and
both are left subtrees of the vertically drawn path $\pi^{\prime}$. As above
one argues that hence $v_{2}$ is drawn on the top right corner of the bounding
box $B(T_{v_{2}})$ of $T_{v_{2}}$, and one unit left of $v_{1}$. Repeating the
argument, each $v_{i}$ is drawn one unit further left that $v_{i-1}$.
Therefore $B(T_{v_{1}})$ has width at least $k\in\Omega(n)$. We also know that
$B(T_{v_{1}})$ has height at least $k$ since its tree has height $k$ and is
drawn strictly upward. So the area is $\Omega(n^{2})$. ∎

So in our constructions, we relax some of the conditions (P6)-(P8), and show
that then we can achieve subquadratic-area GLR-drawings.

###  3.1 Upward 1-bend GLR-drawings

Let $T$ be an ordered rooted tree, and let $\pi=\langle
v_{1},v_{2},\dots,v_{\ell}\rangle$ be a root-to-leaf path of $T$. We give a
simple recursive construction to compute a strictly-upward generalized LR-
drawing of $T$ by using at most one bend per edge. Refer to Figure 8 for an
illustration.

Figure 8: Construction for 1-bend generalized LR-drawings.

Assume $v_{1}$ is placed at an arbitrary point of the plane. For ease of
notation, let $L^{(1)},\dots,L^{(l_{1})}$ be the left subtrees rooted at
$v_{1}$, enumerated from left to right. Recursively compute a drawing for each
$L^{(i)}$, $1\leq i\leq l_{1}$, and denote by $B(L^{(i)})$ the corresponding
bounding box. Place the drawing of $L^{(1)}$ such that the top side of
$B(L^{(1)})$ is one unit below $v_{1}$ and so that the right side of
$B(L^{(1)})$ is one unit to the left of $v_{1}$. Similarly, for each $1<i\leq
l_{1}$, place the drawing of $L^{(i)}$ such that that the top side of
$B(L^{(i)})$ is two units below the bottom side of $B(L^{(i-1)})$ and so that
the right side of $B(L^{(i)})$ is one unit to the left of $v_{1}$. Let
$R^{(1)},\dots,R^{(r_{1})}$ be the right subtrees at $v_{1}$, enumerated from
right to left. Apply a symmetric construction as for the left subtrees and
move them down such that the top side of $B(R^{(1)})$ is placed one unit below
the bottom side of $B(L^{(l_{1})})$. Now place $v_{2}$ vertically aligned with
$v_{1}$ and one unit below the bottom side of $B(R^{(r_{1})})$. Concerning the
edges, observe that the edge connecting $v_{1}$ to the root of $L^{(1)}$ can
be drawn with a straight-line segment without crossings, whereas the other
edges that connect $v_{1}$ to the root of each subtree $L^{(i)}$, with $i>1$,
can instead be drawn with precisely one bend placed one unit above the top
side of $B(L^{(i)})$ and one unit to the left of $v_{1}$. The edges that
connect $v_{1}$ to the roots of the subtrees $R^{(i)}$ are drawn
symmetrically. By repeating the construction for each $v_{i}$, with
$1<i\leq\ell$, we conclude the drawing.

Every row contains a node or a bend, so the height is $O(n)$. The width obeys
Eq. 1. When path $\pi$ is chosen as prescribed by Lemma 2, Chan [2] proved
that Eq. 1 solves to $O(n^{0.48})$. The next lemma follows.

######  Lemma 5.

Any ordered rooted tree of size $n$ admits a strictly-upward GLR-drawing with
at most one bend per edge, whose width is $O(n^{0.48})$ and whose height is
$O(n)$.

Note that the above GLR-drawings can be vertically stretched so to become
straight-line and hence an ideal GLR-drawing. Namely, for each edge $(u,v)$
drawn with one bend, it suffices to insert sufficiently many rows above the
bend point so to guarantee a direct line of sight between $u$ and $v$. This is
always possible because each bend point is such that no other node or bend is
placed with the same $y$-coordinate. While the above transformation does not
change the width of the drawing, it may produce a height that is not
polynomial in $n$. Also, it does not satisfy (P8). (The drawing of Lemma 5
does not satisfy (P8) either because of the rows for the bends, but at least
it comes close.)

###  3.2 Non-upward straight-line LR-drawings

In this section, we show how we can avoid using bends. Thus we create a GLR-
drawing that is straight-line, and in fact satisfies all of (P3)-(P8) except
that it is not upward. The crucial idea is to give two drawing-algorithms to
create different types of GLR-drawings.

  * •

In a type-I drawing, the root is located in the top row (with no restriction
on the column).

  * •

In a type-II drawing, the root is located in the leftmost or rightmost column,
with no node above it in the same column. We will use type-II$\ell$ and type-
II$r$ to specify whether the root is left or right.

######  Lemma 6.

Let $p=0.48$. Given any ordered rooted tree $T$ of size $n$, there exist

  * •

a straight-line GLR-drawing of type I that has width at most $cn^{p}-1$ (for
some constant $c>0$),

  * •

a straight-line GLR-drawing of type II$\ell$ that has width at most $cn^{p}$
(for the same constant $c$), and

  * •

a straight-line GLR-drawing of type II$r$ that has width at most $cn^{p}$ (for
the same constant $c$).

Furthermore, all drawings have height $n$.

###### Proof.

If $T$ consists of a single node then the claim holds trivially. Otherwise,
pick a path $\pi=\langle v_{1},\dots,v_{\ell}\rangle$ with Lemma 2.

We first explain how to create type-I drawings, which is very similar to
Section 3.1 except that we use type-II drawings to avoid bends. Assume $v_{1}$
is placed at an arbitrary point of the plane. Let $L^{(1)},\dots,L^{(l_{1})}$
and $R^{(1)},\dots,R^{(r_{1})}$ be as in Section 3.1. Recursively compute
drawings as follows:

  * •

a type-I drawing for $L^{(1)}$ and $R^{(1)}$,

  * •

a type-II$r$ drawing for each $L^{(i)}$, $2\leq i\leq l_{1}$, and

  * •

a type-II$\ell$ drawing for each $R^{(i)}$, $2\leq i\leq r_{1}$.

Place the drawings as in Section 3.1, except leave only one unit vertical
distance between the bounding boxes. As before, the edges from $v_{1}$ to the
roots of $L^{(1)}$ and $R^{(1)}$ can be drawn straight-line without crossing.
The edges to all other children can now also be drawn straight-line since
those children are in an adjacent column to $v_{1}$.

Any left subtree $\alpha$ uses at most $c|\alpha|^{p}$ columns and any right
subtree $\beta$ uses at most $c|\beta|^{p}$ columns by induction, so by Lemma
2 the width is at most

$c|\alpha|^{p}+c|\beta|^{p}+1\leq c(1-\delta)n^{p}+1\leq cn^{p}-1$

for the constant $\delta>0$ from Lemma 2 and assuming $c$ is sufficiently
large.

Figure 9: Constructions of straight-line drawings with linear height. (Left)
Type-I drawings. (Right) Type-II$\ell$ drawings.

Now we turn towards type-II drawings and only explain how to create a type-
II$\ell$ drawing; the other type is symmetric. Let $\pi=\langle
v_{1},\dots,v_{\ell}\rangle$, and let $k\geq 1$ be the minimal index such that
$v_{k}$ has a left subtree. (If there is no such $v_{k}$ then the type-I
drawing is in fact a type-II$\ell$ drawing.) We draw $v_{1},\dots,v_{k-1}$ as
we did for type-I drawings; since they do not have left subtrees this places
$v_{1},\dots,v_{k-1}$ in the leftmost column. At $v_{k}$, we proceed as
follows:

  * •

As in Section 3.1, let $L^{(1)},\dots,L^{(l_{k})}$ and
$R^{(1)},\dots,R^{(r_{k})}$ be the left and right subtrees at $v_{k}$.

  * •

We use a type-II$\ell$ drawing for $R^{(1)},\dots,R^{(r_{k})}$, and denote by
$B(R^{(i)})$ the corresponding bounding box. Place the drawing of $R^{(1)}$
such that the top left of $B(R^{(1)})$ is one unit below the bottom left
corner of the bottommost subtree of $v_{k-1}$. (If $k=1$, then place $R^{(1)}$
arbitrarily.) For $i=2,\dots,r_{k}$, place the drawing of $R^{(i)}$ such that
the top left corner of $B(R^{(i)})$ is one unit below the bottom left corner
of $B(R^{(i-1)})$.

  * •

Place $v_{k}$ in the next row below. If $k>1$, place $v_{k}$ vertically below
$v_{k-1}$. If $k=1$ and $r_{1}>0$, place $v_{k}$ such that it is one unit to
the left of $B(R^{(1)})$. If $k=1$ and there was no right subtree, then place
$v_{k}$ arbitrarily.

  * •

Let $S(\pi)$ be the subtree rooted at $v_{k+1}$ (thus containing the rest of
$\pi$). Use a type-I drawing for $S(\pi)$, and place it in the rows below
$v_{k}$, with the left side of $B(S(\pi))$ one unit to the right of $v_{k}$.

  * •

We use a type-II$\ell$ drawing for $L^{(1)},\dots,L^{(l_{k})}$. We know that
$l_{k}>0$ by choice of $k$. If $l_{k}>1$, then place $L^{(l_{k})}$ such that
the top left corner of $B(L^{(l_{k}))})$ is one unit below the bottom left
corner of $B(S(\pi))$. For $i$ from $l_{k}-1$ down to 2, place the drawing of
$L^{(i)}$ such that the top left corner of $B(L^{(i)})$ is one unit below the
bottom left corner of $B(L^{(i+1)})$. Finally, place the drawing of $L^{(1)}$
in the next rows such that the top left corner of $B(L^{(1)})$ is exactly
below $v_{k}$.

Thus, as in [4], the vertically drawn path is not the path $\pi$ that we
started out with, instead it is $v_{1},\dots,v_{k}$ plus the vertically-drawn
path of $L^{(1)}$. But still we obtain a GLR-drawing. To prove that this
drawing has the appropriate width, we need an observation.

######  Claim 2.

Let $T^{\prime}$ be a left or right subtree of path $\pi$ chosen with Lemma 2.
Then $T^{\prime}$ has size at most $(1-\delta)^{1/p}n$, for the constant
$\delta>0$ from Lemma 2.

###### Proof.

This follows directly from the bound in the lemma since necessarily
$|T^{\prime}|^{p}\leq(1-\delta)n^{p}$. ∎

Therefore, at any subtree other than $S(\pi)$, the width is by induction at
most $1+c(1-\delta)n^{p}\leq cn^{p}$ for sufficiently large $c$. At subtree
$S(\pi)$, the recursively obtained type-I drawing has width at most
$cn^{p}-1$, and so the width again is at most $cn^{p}$ as desired.

In all cases, we never insert empty rows between drawings, so every row
contains exactly one node and the height is $n$ as desired. ∎

As in Section 3.1, we can stretch the drawing vertically to make it upward, by
moving all subtrees at $v_{k}$ downward and leaving a sufficiently large gap
between $B(R^{(r_{k})})$ and $B(S(\pi)))$ so that edge $(v_{k},v_{k+1})$ can
be routed straight-line. (Details are left to the reader.) Again the height
may not be polynomial and condition (P8) no longer holds.

###  3.3 Upward straight-line LR-drawings

As shown in the previous sections, we can achieve width $O(n^{0.48})$, but the
drawings are either not straight-line, or not upward, or have large (possibly
super-polynomial) height. In this section, we show that with a different
construction, we can bound the height to be $O(n^{1.48})$ in a straight-line,
upward GLR-drawing of width $O(n^{0.48})$. The area hence is $O(n^{1.96})$,
just barely under the trivial $O(n^{2})$ bound.

The idea for this is to follow a different approach of Chan (‘Method 4’) for
tree-drawing; here we occasionally double the height used for some subtrees,
but this happens rarely enough that overall the height can still be bounded.
Chan’s Method 4 does not produce GLR-drawings (he lets the largest subtree re-
use the column of the vertical path) but we can modify the approach at the
cost of increasing the width by one unit. To compensate for this we use a
type-I drawing for the largest subtree, so that the overall width does not
increase too much.

So again we have drawing-types. One of them is exactly the type-I drawing used
in the previous section. The other one, which we call type-III drawing, has
the root located in the top left or top right corner; we use type-III$\ell$
and type-III$r$ to specify whether the root is left or right.

######  Lemma 7.

Let $p=0.48$. Given any ordered rooted tree $T$ of size $n$, there exist

  * •

a straight-line upward GLR-drawing of type I that has width at most $cn^{p}-1$
(for some constant $c>0$),

  * •

a straight-line upward GLR-drawing of type III$\ell$ that has width at most
$cn^{p}$ (for the same constant $c$), and

  * •

a straight-line upward GLR-drawing of type III$r$ that has width at most
$cn^{p}$ (for the same constant $c$).

Furthermore, all drawings have height at most $2n^{1+p}$.

###### Proof.

1 If $T$ consists of a single node then the claim holds trivially. Otherwise,
pick a path $\pi$ with Lemma 2, so that
$|\alpha|^{p}+|\beta|^{p}\leq(1-\delta)n^{p}$ for any left and right subtrees
$\alpha,\beta$ of the path. The creation of a type-I drawing is exactly as in
the previous section, except that we use type-III drawings in place of type-II
drawings so that we have an upward drawing. Using $H(\cdot)$ to denote the
height, we have $H(n)\leq\sum_{i=1}^{d}H(n_{i})+1$ where $d$ is the number of
subtrees and $n_{i}$ is the size of the $i$th subtree. Since $n_{i}\leq n$ and
$\sum_{i}n_{i}=n-1$ we have

$\sum_{i=1}^{d}H(n_{i})+1\leq\sum_{i=1}^{d}2n_{i}n^{p}+2n^{p}\leq
2n^{p}(\sum_{i=1}^{d}n_{i}+1)=2n^{1+p}.$

To construct type-III drawings, we proceed much as in Chan [2], Method 4. Fix
$A=n/2^{1/p}>0.23n$. (The value of $A$ is different from Chan’s, but its use
is nearly the same.) We will completely disregard path $\pi$ and instead pick
one subtree of the root based on $A$. To simplify notations, let
$S_{1},\dots,S_{d}$ be the subtrees at the root, enumerated from left to
right. We only explain how to construct a type-III$\ell$ drawing; constructing
type-III$r$ drawings is symmetric. We have two cases:

Case 1: Either $d\leq 2$ or the subtrees $S_{2},\dots,S_{d-1}$ all have size
at most $n-A$. In this case, recursively construct a type-III$\ell$ drawing
for $S_{1},\dots,S_{d-1}$ and a type-I drawing for $S_{d}$. Combine these
drawings with the standard method that was used already in Lemma 3, see also
Figure 10. Clearly this is a planar order-preserving straight-line upward
drawing, and its height is $1+\sum_{i}H(n_{i})\leq 2n^{1+p}$ with the same
analysis as for type-I drawings. The width $W(n)$ is at most
$1+(cn^{p}-1)=cn^{p}$ at $S_{d}$, and at most $W(n-1)\leq cn^{p}$ at $S_{1}$.
At any other subtree $S_{i}$, the size is at most $n-A<0.77n$, and the width
is at most $1+W(0.77n)\leq 1+c(0.77)^{p}n^{p}\leq cn^{p}$, assuming $c$ is
sufficiently large.

Figure 10: Constructions of type-III$\ell$ straight-line upward drawings with
subquadratic area. (Left) Case 1. (Right) Case 2.

Case 2: $d\geq 3$ and at least one subtree $S_{k}$ with $1<k<d$ has size $n-A$
or more. In this case, use a type-I drawing for $S_{k}$ and $S_{d}$, and a
type-III$\ell$ drawing for all other subtrees.

We explain how to build the drawing in Figure 10 bottom-up. Place the drawing
of $S_{1}$ arbitrarily. Place $S_{2},\dots,S_{k}$ on top of this, with one
unit between their bounding boxes, such that the left sides of their bounding
boxes are one unit to the right of the root of $S_{1}$. Now place an imaginary
$W^{\prime}\times H^{\prime}$ rectangle $R$ with its left side aligned with
the left side of $B(S_{1})$ and its bottom side coinciding with the top side
of $B(S_{k})$. Here
$W^{\prime}=\max\\{|S_{k}|^{p},\max_{i>k}\\{2W(|S_{i}|)\\}$, while
$H^{\prime}=3+2\sum_{i>k}H(|S_{i}|)$. In particular, the top right quadrant of
$R$ is big enough to accommodate the drawings of $S_{k-1},\dots,S_{1}$, plus
one and a half rows. We place the root at the top left corner of $R$. We place
the drawings of $S_{k-1},\dots,S_{1}$ (in this order) below the root and in
the top right quadrant of $R$, with the left sides of their bounding boxes
aligned and unit vertical distance between boxes. Note that this does not use
the center-point of $R$ (which is not a grid point due to the odd height of
$R$). The root of $S_{k}$ is somewhere along the bottom of $R$, hence the edge
from it to the root of $T$ does not enter the top right quadrant of $R$ and
the drawing is planar. Clearly it is a GLR-drawing and also strictly upward.
In fact, conditions (P3)-(P7) are all satisfied (but (P8) is not).

We first analyze the width. At $S_{k}$, the width is at most $1+(cn^{p}-1)\leq
cn^{p}$ by induction. At any other subtree $S_{i}$, the size is $n_{i}\leq
A=n/2^{1/p}$ and the width is at most

$\max\\{1+W(|S_{i}|),2W(|S_{i}|)\\}\leq 2\cdot
c\left(\tfrac{n}{2^{1/p}}\right)^{p}=cn^{p}$

as desired. As for the height, $S_{k}$ contributes at most $2n_{k}^{1+p}$ rows
and any other subtree $S_{i}$ contributes at the most $2\cdot 2n_{i}^{1+p}$
rows. We need two further rows for $R$ (the bottom row was already counted).
Since $n_{i}\leq A=n/2^{1/p}$ for $i\neq k$ and $\sum_{i}n_{i}=n-1$, the
height is at most

$2+2n^{p}n_{k}+\sum_{i\neq k}4\left(\tfrac{n}{2^{1/p}}\right)^{p}n_{i}\leq
2n^{p}+2n^{p}\sum_{i=1}^{d}n_{i}=2n^{1+p}$

as desired. ∎

##  4 Remarks

In this paper, we studied how to generalize the concept of LR-drawings that
was previously designed for binary trees [2, 4, 8] to trees of higher arity.
To this end, we first generalized a lemma by Chan about paths for which
$|\alpha|^{p}+|\beta|^{p}\leq(1-\delta)n^{p}$ for constant $p=0.48$,
$\delta>0$ and any left and right subtree $\alpha,\beta$. Then we explained
how to use this path to construct generalized LR-drawings of width
$O(n^{0.48})$ and subquadratic area, both with and without the restriction on
the drawing being straight-line and/or upward. We conclude the paper by
listing some open problems

  * •

The most natural open problem is to close the gap on the width of GLR-
drawings. Frati et al. showed that width $\Omega(n^{0.418})$ is sometimes
required [8], and Chan and Huang improved this to $\Omega(n^{0.428})$ [4].
These lower bounds were for binary trees; could they perhaps be strengthened
if we allow higher arity? Using ternary trees, one can immediately reduce the
size of the lower-bound tree $T_{h}$ of [4, 8], by $2^{h}-1$ (contract every
second edge of path $\pi$) without affecting the validity of the lower-bound
proof. Unfortunately, this improves the lower bound only by a lower-order
term.

  * •

We showed that in a GLR-drawing where all additional conditions (P3)-(P8) are
satisfied, the width must be $\Omega(n)$. Is there an intermediate lower bound
that shows up when requiring other subsets of these properties? We are
especially curious about removing condition (P5) (‘grouping of left/right
subtrees’), which seems very artificial but is crucially required in the proof
of Lemma 4.

  * •

Chan and Huang improved the width of LR-drawings of binary trees [4]. The main
idea is that rather than drawing one chosen path $\pi$ as a straight-line,
they add an ‘$i$-twist’ to the drawing of path $\pi$, using $2^{i}$ non-
vertical edges for $\pi$ while the corresponding other subtrees at these edges
use vertical lines. With this, they can achieve an LR-drawing of width
$O(n^{0.438})$ (and even smaller with further improvements).

It would be interesting to see whether this approach could be generalized to
trees of higher arity. We cannot generalize the algorithm directly, because
the subtrees that use vertical lines are defined via a size-property. In trees
of higher arity these subtrees may well have common parents on $\pi$, making
it impossible to use distinct vertical lines for them, as is necessary in the
construction.

  * •

Our construction of ideal GLR-drawings achieves subquadratic area, but barely.
Can the area be improved?

## References

  * [1] T. Biedl.  Ideal drawings of rooted trees with approximately optimal width.  Journal of Graph Algorithms and Applications, 21(4):631–648, 2017\.
  * [2] T. M. Chan.  A near-linear area bound for drawing binary trees.  Algorithmica, 34(1):1–13, 2002.
  * [3] T. M. Chan.  Tree drawings revisited.  Discret. Comput. Geom., 63(4):799–820, 2020.
  * [4] T. M. Chan and Z. Huang.  Improved upper and lower bounds for LR drawings of binary trees.  In D. Auber and P. Valtr, editors, Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers, volume 12590 of Lecture Notes in Computer Science, pages 71–84. Springer, 2020.
  * [5] G. Di Battista and F. Frati.  Small area drawings of outerplanar graphs.  Algorithmica, 54(1):25–53, 2009.
  * [6] G. Di Battista and F. Frati.  A survey on small-area planar graph drawing, 2014.  CoRR report 1410.1006.
  * [7] F. Frati.  Straight-line orthogonal drawings of binary and ternary trees.  In Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers, pages 76–87, 2007\.
  * [8] F. Frati, M. Patrignani, and V. Roselli.  LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs.  J. Comput. Syst. Sci., 107:28–53, 2020.
  * [9] A. Garg and A. Rusu.  Area-efficient order-preserving planar straight-line drawings of ordered trees.  Int. J. Comput. Geometry Appl., 13(6):487–505, 2003.
  * [10] A. Garg and A. Rusu.  Area-efficient planar straight-line drawings of outerplanar graphs.  Discrete Applied Mathematics, 155(9):1116–1140, 2007.