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 2033405938 2053113908
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. Abstract The path-width of a graph is the minimum value of k such that the graph can be obtained from a sequence of graphs G 1 ,…,G r each of which has at most k + 1 vertices, by identifying some vertices of G i pairwise with some of G i+1 ( 1 ≤ i ). For every forest H it is proved that there is a number k such that every graph with no minor isomorphic to H has path-width ≆k . This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that if P is any property of graphs such that some forest does not have property P , then the set of minor-minimal graphs without property P is finite. Abstract Let S be a set of N grid points in the plane, no two of which lie on the same horizontal or vertical line, and let G be a graph with n vertices ( n ⩽ N ). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is a chain of horizontal and vertical segments with bends on grid points whose length is equal to the Manhattan distance of its end vertices. We study the following problem. Given a family F of trees, what is the minimum value f ( n ) such that every n -vertex tree in F admits an orthogeodesic point-set embedding on every set of grid points of size f ( n ) such that no two points lie on the same horizontal or vertical line? We provide polynomial upper bounds on f ( n ) for both planar and non-planar orthogeodesic point-set embeddings as well as for the case when edges are required to be L -shaped.