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 of the set and every edge is drawn as a sequence of two axis-aligned line segments. Let f_d(n) denote the minimum number N of points such that every n-vertex tree with maximum degree d\in\{3,4\ admits an L-shaped embedding in every point set of size N, where no two points have the same abscissa or ordinate. The best known upper bounds for this problem are f_3(n)=O(n^{1.22 However, no lower bound besides the trivial bound f_d(n) \geq n is known to this date . 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 , proving that f_4(n)\geq n+1 for those n . Moreover, using computer assistance , we show that every tree on n\leq 11 vertices admits an L-shaped embedding in every set of n points , proving that f_d(n) = n, d\in\{3, 4\ .
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 .
D
of the set
R
Let f_d(n) denote the minimum number N of points such that every n-vertex tree with maximum degree d\in\{3,4\
There has been considerable work on establishing upper bounds on the minimum cardinality such that any point set of that size
R
in every point set of size N, where no two points have the same abscissa or ordinate. The best known upper bounds for this problem are f_3(n)=O(n^{1.22
of any n-vertex tree with maximum degree 4.
R
lower bound besides the trivial bound f_d(n) \geq n
non-trivial lower bound
R
.
, i.e., no known n-vertex tree requires more than n points to be embedded.
D
, proving that f_4(n)\geq n+1 for those n
R
assistance
help
R
11
12
R
, proving that f_d(n)
. 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
R
n, d\in\{3, 4\
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