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.
When point sets are chosen uniformly at random, i.e., the @math -coordinates are a random permutation, it is known that @math and @math points are sufficient to embed any tree with maximum degree 3 or 4, respectively, with probability at least @math [Chapter 4] scheucher2015 (see also @cite_5 ).
@cite_5
2545825365 2552511935 2125271247 2950981509
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. 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. Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability @math , independently of each other, and a deterministic spreading rule with a fixed parameter @math : if a vacant site has at least @math occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on @math ; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of @math for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than @math , then the critical probability is 1, while it is @math on the @math -ary tree. A related result is that in any rooted tree @math there is a way of erasing @math children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree @math has branching number @math . We also prove that on any @math -regular non-amenable graph, the critical probability for the @math -rule is strictly positive. Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure.