An L-shaped embedding of a tree in a point set is a planar drawing of the tree where the vertices are mapped to distinct points and every edge is drawn as a sequence of two axis-aligned line segments. There has been considerable work on establishing upper bounds on the minimum cardinality such that any point set of that size admits an L-shaped embedding of any @math -vertex tree with maximum degree 4. However, no non-trivial lower bound is known to this date, i.e., no known @math -vertex tree requires more than @math points to be embedded. In this paper, we present the first examples of @math -vertex trees for @math that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on @math vertices admits an L-shaped embedding in every set of @math points. We also consider embedding ordered trees, where the cyclic order of the neighbors of each vertex in the embedding is prescribed. For this setting, we determine the smallest non-embeddable ordered tree on @math vertices, and we show that every ordered tree on @math or @math vertices admits an L-shaped embedding in every set of @math points. We also construct an infinite family of ordered trees which do not always admit an L-shaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.
In this paper we consider planar L-shaped embeddings of trees in point sets, that is, planar drawings where the vertices are mapped to a subset of the given points and where every edge consists of two axis-aligned line segments. We investigate the minimum number m, such that any n vertex tree with maximum degree 4 admits a planar L-shaped embedding in any point set of size m. First we give an upper bound O(n c ) with c = log2 3 1:585 for the general case, and thus answer the question by Di [4] whether a subquadratic upper bound exists. Then we introduce the saturation function for trees and show that trees with low saturation can be embedded even more eciently. In particular, we improve the upper bound for caterpillars and extend the class of trees that require only a linear number of points. In addition, we present some probabilistic results for either randomly chosen trees or randomly chosen point sets.