Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00537
On Lshaped point set embeddings of trees: first nonembeddable examples
Vol. 24, no. 3, pp. 343369, 2020. Regular paper.
Abstract An Lshaped 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 axisaligned 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 Lshaped embedding on the point set.
However, no nontrivial 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 Lshaped embedding.
Moreover, using computer help, we show that every tree on $n\leq 12$ vertices admits an Lshaped 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 nonembeddable ordered tree on $n=10$ vertices, and we show that every ordered tree on $n\leq 9$ or $n=11$ vertices admits an Lshaped embedding in every set of $n$ points.
We also construct an infinite family of ordered trees which do not always admit an Lshaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.

Submitted: November 2019.
Reviewed: March 2020.
Revised: May 2020.
Accepted: June 2020.
Final: June 2020.
Published: July 2020.
Communicated by
Giuseppe Liotta

Journal Supporters
