Using your Head is Permitted

December 2010 solution

It is not difficult to embed cliques of arbitrarily large size even using only single-bend joints, given that the Euclidean dimension of the embedding range is high enough. For example, Kn+1 can be embedded onto Rn by setting one vertex in the origin and each of the n other vertices at the endpoints of the standard basis vectors, e1,...,en. Edges to and from the origin are mapped into straight lines (no bends), whereas edges from ei to ej follow a single-bend path, with the bend at ei+ej. This embedding can easily be shown to have no overlapping paths: the path of any ei-to-ej edge mapping lies entirely on points passing through the plane connecting the points ei, ej and the origin and contains no points shared by any other such ek-el-0 plane. The path of any ei-to-0 edge, on the other hand, lies through the line connecting these points, and, again, this line contains no part of the path of any other edge.

However, because we want the maximal-sized clique embeddable in Rn, we are looking to embed K2n+1. Clearly, no larger cliques are possible, because there are only 2n axis-parallel directions, so no vertex can be connected by more than 2n non-overlapping paths whose initial segments are axis-parallel and joining in a single point.

To do this, let us consider vertices at the origin and at ± each of e1,...,en. To be able to easily ascertain that the construction is valid, all edges will be planar, as in our first construction. Specifically, edges running from ±ei to ±ej will be mapped entirely onto the plane running through ei, ej and the origin. Edges running between ei and -ei will also be on an ei-ej-0 plane, where j will be decided by use of a 1-1 function from i. For example, we can choose j=i+1 (mod n). Similarly, edges running between ±ei and 0 will be mapped entirely onto an ei-ej-0 plane, where j will be decided by use of a 1-1 function from i. In this case, we can choose, for example, j=i+2 (mod n).

If we consider n≥5, cases 1, 2 and 3 in the image below cover every choice of an ei-ej-0 plane. They show cross-sections of a general embedding of K2n+1 in Rn.

In particular, they present a solution to the R5 problem.

Embedding K9 in R4 is a little more tricky, because some of our plane choices begin to overlap. For example, when i=1 we choose j=3 for the e1-to-0 edge, but when i=3 we choose j=1. This leads both edges to be on the same plane: the one passing through e1, e3 and the origin.

Case 4 in the image above shows how to resolve the resulting difficulties, and presents a solution to R4.

Things become even trickier in R3, where no set of plane-embedded edges seems to provide a valid solution. To solve this case, we are forced to off-center the central vertex. For reasons of symmetry, we will place it at (-0.5,-0.5,-0.5). All edges other than those connecting with this central vertex will still be planar, as before.

The image below shows two solutions for this case. In each image, the dashed lines represent path segments that are not on any ei-ej-0 plane.

There are three axis-parallel plane directions in R3. Choosing either of the two constructions presented for each of these yields a solution for embedding K7 in R3. It is possible to mix-and-match. Up to symmetries, these are 4 different solutions, depending on how many times one picks the first construction and how many times one picks the second.

The notion that K7 is embeddable in R3 at all is fairly new. It was first shown to be possible only as late as 2000, in David Wood's doctoral thesis. (Up until then this embedding was conjectured not to exist, even though, today, even a simple branch-and-bound program can discover a great many such embeddings in a fairly short run.) Wood describes, in his thesis, a K7 equivalent to choosing "Construction 1" in all three planes. The thesis continues to prove the possibility of embedding K2n+1 in Rn for any n≥3, but does so for higher dimensions using constructions somewhat different than what is presented here.

David Wood's complete thesis can be found here. Also on the same page is a picture of David Wood (right) and Graham Farr (left) along with two wood-and-metal models of 3-D 2-bend point graph embeddings. The left one is K6 and the right one is K7.

Lastly, we reach R2. As we have seen, as one lowers n, the difficulty of finding an embedding of K2n+1 in Rn continuously increases. In n=2 this is actually impossible. The reason for this is that K5 is not a planar graph. However, K4 is embeddable trivially.

For completion, the following links provide text files that solve all four problems.


Last note: in the literature, the common terminology for this sort of embedding is "orthogonal graph drawing".

Back to riddle

Back to main page