Subgraph isomorphism problem on 2d triangular lattices.

Question

Is there an efficient (possibly probabilistic/approximate) algorithm for determining whether a particular graph is the subgraph of an infinite two dimensional triangular lattice? How about three dimensional?

For context, we are interested in the question whether a graph can be geometrically embedded in 2d with fixed edge lengths, with new edges formed whenever two vertices come close enough to each other. The above combinatorial problem seems to approximate this behaviour well enough for our purposes.

P.S.: I apologize if this question is too elementary, coming from a different field I have so far failed to find the correct way to phrase it to google.

Answer 1

There exists a polynomial-time reduction from the NP-complete partition problem (special case of the subset sum problem) to determining whether a finite graph is a subgraph of the triangular lattice. For example, with the multiset $S = \{ 5, 1, 2, 6, 16, 6, 6, 6\}$, the corresponding graph (together with the embedding for the partition $\{ 5, 1, 2, 16 \} \cup \{ 6, 6, 6, 6 \}$) is shown below:

In particular, the `outer wall' of this graph must be embedded rigidly (i.e. congruent to the embedding in the image above), and the septum is also forced (since the total length of the path is equal to the Euclidean distance between the vertices it joins). For each of the paths attached to the septum, it can either be contained in the upper or lower region. Hence, this graph has an embedding only if there is a solution to the partition problem.

The converse is not true for general sets of positive integers (due to geometric constraints, a valid partition need not yield an embedding of the corresponding graph), although I claim that any set can be reduced to one with this property. Specifically, one can multiply every element of the set by the same positive integer $N$, resulting in an equivalent problem where the paths are longer. If $N$ is sufficiently large (compared with the cardinality $|S|$) and the regions are parallelograms (possible if $|S|$ divides $N$), then a greedy algorithm is capable of positioning the paths such that they do not intersect.