Moser Spindle - Other Properties and Applications

Other Properties and Applications

The Moser spindle is a planar graph, meaning that it can be drawn without crossings in the plane. However, it is not possible to form such a drawing with straight line edges that is also a unit distance drawing; that is, it is not a matchstick graph. The Moser spindle is also a Laman graph, meaning that it forms a minimally rigid system when embedded in the plane. As a planar Laman graph, it is the graph of a pointed pseudotriangulation, meaning that it can be embedded in the plane in such a way that the unbounded face is the convex hull of the embedding and every bounded face is a pseudotriangle with only three convex vertices.

The complement graph of the Moser graph is a triangle-free graph. Thus, the unit distance embedding of the Moser graph may be used to solve the problem of placing seven points in the plane in such a way that every triple of points contains at least one pair at unit distance from each other.

Adding any edge to the Moser spindle results in a graph that cannot be embedded in the plane as a unit distance graph, and there does not exist a graph homomorphism from the Moser spindle to any smaller unit distance graph. These two properties of the Moser spindle were used by Horvat, Kratochvíl & Pisanski (2011) to show the NP-hardness of testing whether a given graph has a two-dimensional unit distance representation; the proof uses a reduction from 3SAT in which the Moser spindle is used as the central truth-setting gadget in the reduction.

The Moser spindle can also be used to prove a result in Euclidean Ramsey theory: if T is any triangle in the plane, and the points of the plane are two-colored black and white, then there is either a black translate of T or a pair of white points at unit distance from each other. For, let M be a unit-distance embedding of the Moser spindle, and let M + T be the Minkowski sum of M and T. If M + T has no white unit-distance pair, then each of the three copies of the Moser spindle in M + T must have at most two white points, because the white points in each copy must form an independent set and the largest independent set in the Moser spindle has size two. Therefore, among the seven vertices of the Moser spindle, there are at most six that have a white copy in M + T, so there must be one of the seven vertices all of whose copies are black. But then the three copies of this vertex form a translate of T.