# Subgraph isomorphism problem on 2d triangular lattices.

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.

-
What do you mean by "with new edges formed whenever two vertices come close enough to each other"? For the exact question, a useful result might be that the chromatic number of such graphs is bounded: en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem –  Ben Barber Apr 10 '13 at 15:25

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:
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.