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.
Besides the problem of finding L-shaped embeddings of arbitrary trees in arbitrary point sets, various special classes of trees and point sets have also been studied. For instance, perfect binary and perfect ternary @math -vertex trees can be embedded in any point set of size @math or @math , respectively @cite_3 . Moreover, trees with pathwidth @math can be embedded in any set of @math points [Chapter 3.3.2] scheucher2015 (see also @cite_5 ). For the definition of pathwidth, we refer the reader to @cite_7 . Specifically, any @math -vertex caterpillar with maximum degree 3 can be embedded in any point set of size @math @cite_6 . A is a tree with the property that all leaves are in distance 1 of a central path. For maximum degree 4 caterpillars, the currently best known upper bound is @math many points [Chapter 5.2.1] scheucher2015 . @cite_3 showed that any ordered caterpillar can be embedded in any point set of size @math .
@cite_5 @cite_7 @cite_3 @cite_6
2552511935 2545825365 2199357291 2570705339
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. Consider a uniform random rooted tree on vertices labelled by @math , with edges directed towards the root. We imagine that each node of the tree has space for a single car to park. A number @math of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider @math and let @math denote the event that all @math cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if @math , we have @math , whereas if @math we have @math . We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we are led to consider the following variant of the problem: take the tree to be the family tree of a Galton-Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson( @math ) number of cars arrive at each vertex. Let @math be the number of cars which visit the root of the tree. Then for @math , we have @math , whereas for @math , we have @math . This discontinuous phase transition turns out to be a generic phenomenon in settings with an arbitrary offspring distribution of mean at least 1 for the tree and arbitrary arrival distribution. This paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. The distance distortion between non adjacent vertices can be made arbitrarily small --- less than a (1+e) factor for any given e. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees. This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of @math , with the guarantee that for each @math simultaneously, the distortion of a fraction @math of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion @math . For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion @math . These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the @math distortion is @math . For probabilistic embedding into spanning trees we prove a scaling distortion of @math , which implies constant @math -distortion for every fixed @math .