On L-Shaped Point Set Embeddings of Trees: First Non-embeddable Examples

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; see Fig. 1. Here and throughout this paper, all point sets are such that no two points have the same abscissa or ordinate. The investigation of L-shaped embeddings was initiated in [5,6,7]. In particular, Di Giacomo et al. [5] showed that \(O(n^2)\) points are always sufficient to embed any n-vertex tree, and they asked for a tree that does not admit an L-shaped embedding. Note that an L-shaped embedding of a tree is possible only if the maximum degree of the tree is at most 4. Moreover, if the maximum degree is 2, then the tree is a path and can be embedded greedily on any point set of the same size. Formally, 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.

An L-shaped embedding of a tree in a given point set.

Full size image

The second author’s master’s thesis [11] proposed a method to recursively construct an L-shaped embedding of any n-vertex tree in any point set of size \(O(n^{1.58})\) (see also [1]). Biedl et al. [3] gave a more precise analysis of this method, proving that \(f_3(n)=O(n^{1.22})\) and \(f_4(n)=O(n^{1.55})\) points are enough. No lower bound besides the trivial bound \(f_d(n) \ge n\) is known to this date. However, the authors of the aforementioned paper also considered a more restrictive setting, where the cyclic order of the edges around each vertex in the embedding is prescribed. For this setting they presented a 14-vertex tree which does not admit an L-shaped embedding in a particular point set of size 14, and they raised the problem to find an infinite family of such non-embeddable trees.^{Footnote 1} All of our results in this paper are for the unrestricted setting, that is, there are no constraints on the cyclic order of the edges around each vertex.

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 n-vertex trees can be embedded in any point set of size \(O(n^{1.142})\) or \(O(n^{1.465})\), respectively [3]. Moreover, trees with pathwidth k can be embedded in any set of \(2^kn\) points [11, Chap. 3.3.2] (see also [1]). When point sets are chosen uniformly at random (i.e., the y-coordinates are a random permutation), it is known that \(O(n \log n (\log \log n)^2)\) and \(O(n^{1.332})\) points are enough to embed any tree with maximum degree 3 or degree 4, respectively, with probability at least 1/2 [11, Chap. 4] (see also [1]).

To search for n-vertex trees that do not admit an L-shaped embedding in certain point sets of size n, we formulated a SAT instance to test a given pair of tree and point set for embeddability; see Sect. 4. The solver found an embedding of all pairs of trees and point sets up to size \(n\le 11\). Moreover, we found a 13-vertex tree that does not admit an embedding in a particular point set.

Theorem 1

(Computer-assisted). Every tree on \(n \le 11\) vertices admits an L-shaped embedding in every set of n points, hence \(f_d(n)=n\) for \(n\le 11\) and \(d\in \{3,4\}\).

Theorem 2

The tree \(T_{13}\) in Fig. 2 does not admit an L-shaped embedding in the point set \(P_{13}\) shown in the figure, hence \(f_4(13)\ge 14\).

The tree \(T_{13}\) (left) that does not admit an L-shaped embedding in the staircase point set \(P_{13}\) (right). Each block of \(P_{13}\) is depicted with a different color. (Color figure online)

Full size image

Even though the 13-vertex tree \(T_{13}\) was found using the help of a SAT solver, a human-verifiable proof of Theorem 2 is not hard to obtain; see Sect. 3. Besides the pair \((T_{13},P_{13})\), we also found pairs of trees and point sets that do not admit an embedding for larger values of n; see the full version [9]. Overall, we found trees with \(n\in \{13,14,16,17,18,19,20\}\) vertices, showing that \(f_4(n)\ge n+1\) for those values of n. For \(n=15\), however, our computer search did not yield any non-embeddable example. We remark that all known non-embeddable trees are lobsters (i.e., trees with pathwidth 2) and they contain \(T_{13}\) as a subtree.

As it turns out, the point sets that appear to be difficult for embedding have a regular staircase shape; see Fig. 2.

Definition 1

(Staircase point set). For any partition \(n = a_1 + \ldots + a_k\) with \(k,a_1,\ldots ,a_k \in \mathbb {N}\), the \((a_1,\ldots ,a_k)\)-staircase is the point set consisting of a sequence of k blocks, ordered from top-left to bottom-right, and the i-th block contains a sequence of \(a_i\) points with increasing x- and y-coordinate.

Consider the tree \(T_{13}\) and the point set \(P_{13}\) depicted in Fig. 2. We label the degree 3 vertex of \(T_{13}\) by Y and the three degree 4 vertices of \(T_{13}\) as \(X_1,X_2,X_3\), respectively. Moreover, we label the blocks in the (2, 2, 2, 1, 2, 2, 2)-staircase point set \(P_{13}\) from left to right by \(B_{-3},B_{-2},\ldots ,B_{3}\). Note that \(T_{13}\) is symmetric, as the removal of Y leaves three isomorphic trees. Moreover, \(P_{13}\) has reflection symmetries along both diagonals of the grid.

For the sake of contradiction, we assume that an L-shaped embedding of \(T_{13}\) to \(P_{13}\) exists. We first derive three lemmas that capture to which blocks the vertices \(X_1,X_2,X_3,Y\) can be mapped in such an embedding, and we then complete the proof by distinguishing two main cases.

Lemma 1

Neither of the four vertices \(X_1,X_2,X_3,Y\) is mapped to \(B_{-3}\) (black) or to \(B_{3}\) (purple).

Proof

All points in \(B_{-3}\) and \(B_{3}\) lie on the bounding box of the point set, so if one of the \(X_i\) is mapped onto such a point, then one of the four edges incident with \(X_i\) would leave the bounding box, which is impossible. Moreover, Y cannot be mapped onto one of these two blocks, as otherwise one of the \(X_i\), which are the only neighbors of Y in \(T_{13}\), would be mapped onto the other point of that same block.   \(\square \)

Illustration of the proofs of (a) Lemma 2 and (b) Lemma 3. Crossing edges are highlighted red. (Color figure online)

Full size image

Lemma 2

Each of the \(X_i\) is mapped to a distinct block (distinct color).

Proof

Assume that \(X_i\) and \(X_j\) are mapped to the same block. By symmetry, we may assume that \(X_j\) is right above \(X_i\), and that Y is right below of \(X_i\) and \(X_j\); see Fig. 3(a). Note that the edge \(YX_i\) enters \(X_i\) from below and the edge \(YX_j\) enters \(X_j\) from the right. As \(X_i\) and \(X_j\) both have degree 4, and their block only contains two points, the edge leaving \(X_i\) to the right and the edge leaving \(X_j\) to the bottom must cross, a contradiction.   \(\square \)

Lemma 3

Not all three points \(X_1,X_2,X_3\) lie on the same side (above, below, left or right) of Y.

Proof

It suffices to prove one of the statements, then the others follow by symmetry. Suppose for the sake of contradiction that \(X_1,X_2,X_3\) all lie above Y. As one edge leaving Y has to go right, one of the \(X_i\), say \(X_3\), is mapped to the same block, and Y is left below of \(X_3\) in that block; see Fig. 3(b). Moreover, the edge \(YX_3\) enters \(X_3\) at the bottom. As \(X_3\) has degree 4, and each block contains at most two points, the edge that leaves Y on the top towards \(X_1\) or \(X_2\) crosses the edge that leaves \(X_3\) to the left, a contradiction.   \(\square \)

By Lemmas 1 and 3, Y is mapped to one of the blocks \(B_{-1}\) (orange), \(B_0\) (yellow), or \(B_1\) (green). By Lemma 2 we may assume that \(X_1,X_2,X_3\) appear in distinct blocks in exactly this order from left to right and also from top to bottom, and none of them is in \(B_{-3}\) (black) or \(B_3\) (purple). Moreover, from Lemma 3 we conclude that \(X_1\) and \(X_3\) are in other blocks than Y, so at most Y and \(X_2\) are in the same block. We now distinguish two cases.

Case 1: Y and \(X_2\) are mapped to the same block. By symmetry, we may assume that they are mapped to \(B_{1}\) (green) and that \(X_2\) lies right above Y. Then the vertex \(X_3\) must be mapped to the block \(B_2\) (blue); see Fig. 4(a). If the edge \(YX_3\) would leave Y to the right, then the edge leaving \(X_2\) at the bottom would cross the edge \(YX_3\). It follows that the edge \(YX_3\) leaves Y at the bottom and enters \(X_3\) from the left. Note that the edge that leaves \(X_2\) to the right can only connect to a leaf L that is mapped to \(B_2\cup B_3\), and L must be mapped to the right of \(X_3\), as otherwise the edges \(X_2L\) and \(YX_3\) would cross. The edges leaving \(X_3\) at the bottom and right can only connect to points from \(B_2\cup B_3\), so together with \(X_3\) and L we already have four vertices that are mapped to \(B_2\cup B_3\). Consequently, the edge leaving \(X_3\) at the top must connect to a point outside of \(B_1\cup B_2\cup B_3\), and therefore this edge crosses the edge \(X_2L\), a contradiction.

Illustration of the proof of Theorem 2 in (a) Case 1 and (b) Case 2. (Color figure online)

Full size image

Case 2: Y and \(X_2\) are mapped to distinct blocks, so all four points \(X_1,X_2,X_3,Y\) are in different blocks. By symmetry, we assume that \(X_1\) and \(X_2\) both lie above and left of Y, and \(X_3\) lies below and right of Y. Moreover, we assume that the edge \(YX_1\) enters \(X_1\) from below and that the edge \(YX_2\) enters \(X_2\) from the right; see Fig. 4(b). Note that \(X_2\) cannot connect to any points right of Y, and \(X_1\) can only connect to such points by the edge leaving it to the right. As Y is either mapped to \(B_0\) (yellow) or \(B_1\) (green), there are at most 7 points left above of Y. Therefore, as \(X_1\) and \(X_2\) together with their leaves form a set of 8 points, Y must be mapped to \(B_1\) (green), and exactly one leaf L of \(X_1\) is mapped to a point right of Y, connected to \(X_1\) by the edge that leaves \(X_1\) to the right. Note that \(X_2\) cannot be mapped to \(B_0\) (yellow), as then the edge leaving \(X_2\) at the bottom could not connect to any point without either crossing \(YX_1\) or \(YX_2\). Consequently, \(X_2\) is mapped to \(B_{-1}\) (orange). However, as \(B_{-1}\) and \(B_0\) together contain only 3 points, and \(X_2\) together with its leaves form a set of 4 vertices, at least one of the two edges that leave \(X_2\) to the left or top must connect to a point above or left of \(X_1\), and this edge will cross either the edge \(YX_1\) or \(X_1L\), again a contradiction.

In both cases we obtain a contradiction to the assumption that \(T_{13}\) admits an L-shaped embedding on the point set \(P_{13}\). This completes the proof of Theorem 2.

To test whether a given tree with vertex set \(\{1,\ldots ,n\}\) admits an L-shaped embedding on a given point set \(\{P_1,\ldots ,P_n\}\), we formulated a Boolean satisfiability problem that has a solution if and only if the tree admits an embedding in the point set. Our SAT model has variables \(x_{i,j}\) to indicate whether the vertex i is mapped to the point \(P_j\), and for every edge ab in the tree a variable \(y_{a,b}\) to indicate whether the edge is connected horizontally to a (otherwise it is connected vertically to b). The following constraints are necessary and sufficient to guarantee the existence of an L-shaped embedding:

1. (i)

   Injective mapping from vertices to points: Each vertex is mapped to a point, and no two vertices are mapped to the same point.

2. (ii)

   L-shaped edges: For each edge ab of the tree, a is either connected horizontally or vertically to b.

3. (iii)

   No overlapping edge segments: For each pair of adjacent edges ab and ac, if b and c are mapped to the right of a, then a cannot be connected horizontally to both b and c. An analogous statement holds if b and c are both mapped to the left, above, or below a.

4. (iv)

   No crossing edge segments: For each pair of edges ab and cd, the vertices a, b, c, d must not be be mapped so that segments cross. More specifically, for each four points p, q, r, s (to which a, b, c, d may map), there are at most four cases that have to be forbidden in the mapping, depending on the relative position of p, q, r, s.

The resulting CNF formula thus has \(\Theta (n^2)\) variables and \(\Theta (n^4)\) clauses.

Our Python program that creates a SAT instance for a given pair of tree and staircase point set is available online [10]. The resulting instances can be solved, e.g., using the solver PicoSAT [4].

Theorems 1 and 2 leave open whether all 12-vertex trees embed in all point sets of the same size. In our experiments we were only able to test all 12-vertex trees on certain symmetric point sets of that size. Hence, we would not be surprised if \(T_{13}\) is indeed a minimal non-embeddable example. We currently do not know of any infinite family of trees which do not always admit an L-shaped embedding. Moreover, since all examples that we know are lobsters (trees with pathwidth 2), it would be interesting to know whether caterpillars (trees with pathwidth 1) always admit an L-shaped embedding. So far we only know of trees with maximum degree 4 which do not always admit an L-shaped embedding — the question for trees with maximum degree 3 remains open [5,6,7]. Kano and Suzuki [7] even conjectured that \(f_3(n)=n\).

A more general class of embeddings are orthogeodesic embeddings, where the edges are drawn with minimal \(\ell _1\)-length and consist of segments along the grid induced by the point set [2, 5, 8, 11]. The best known bounds are due to Bárány et al. [2] who showed that every n-vertex tree with maximum degree 4 admits an orthogeodesic embedding on every point set of size \(\lfloor 11n/8\rfloor \). Unfortunately, our example \(T_{13}\) allows an orthogeodesic embedding on \(P_{13}\) (see the full version [9]), so the question whether n points are always sufficient to guarantee an orthogeodesic embedding of any n-vertex tree [2, 5], is still open.