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 n-vertex tree with maximum degree 4. However, no non-trivial lower bound is known to this date, i.e., no known n-vertex tree requires more than n points to be embedded. In this paper, we present the first examples of n-vertex trees for n\in\{13,14,16,17,18,19,20\} that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on n\leq 12 vertices admits an L-shaped embedding in every set of n 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 n=10 vertices, and we show that every ordered tree on n\leq 9 or n=11 vertices admits an L-shaped embedding in every set of n 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.
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 of a point set to guarantee that any tree of the same size with maximum degree 4 admits an L-shaped embedding on the point set. However, no non-trivial lower bound is known to this date, i.e., no known n-vertex tree requires more than n points to be embedded. In this paper, we present the first examples of n-vertex trees for n\in\{13,14,16,17,18,19,20\} that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on n\leq 12 vertices admits an L-shaped embedding in every set of n 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 n=10 vertices, and we show that every ordered tree on n\leq 9 or n=11 vertices admits an L-shaped embedding in every set of n 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.
R
such that any point set of that size admits an L-shaped embedding of any n-vertex tree
of a point set to guarantee that any tree of the same size
R
4.
4 admits an L-shaped embedding on the point set.