  We describe polynomial time algorithms for determining whether an undirected
graph may be embedded in a distance-preserving way into the hexagonal tiling of
the plane, the diamond structure in three dimensions, or analogous structures
in higher dimensions. The graphs that may be embedded in this way form an
interesting subclass of the partial cubes.
