  The first part of the paper centers in the study of embeddability between
partially commutative groups. In [KK], for a finite simplicial graph $\Gamma$,
the authors introduce an infinite, locally infinite graph $\Gamma^e$, called
the extension graph of $\Gamma$. They show that each finite induced subgraph
$\Delta$ of $\Gamma^e$ gives rise to an embedding between the partially
commutative groups $G(\Delta)$ and $G({\Gamma})$. Furthermore, it is proven
that in many instances the converse also holds. Our first result is the
decidability of the Extension Graph Embedding Problem: there is an algorithm
that given two finite simplicial graphs {\Delta} and {\Gamma} decides whether
or not $\Delta$ is an induced subgraph of $\Gamma^e$. As a corollary we obtain
the decidability of the Embedding Problem for 2-dimensional partially
commutative groups. In the second part of the paper, we relate the Embedding
Problem between partially commutative groups to the model-theoretic question of
classification up to universal equivalence. We use our characterisation to
transfer algebraic and algorithmic results on embeddability to model-theoretic
ones and obtain some rigidity results on the elementary theory of atomic pc
groups as well as to deduce the existence of an algorithm to decide if an
arbitrary pc group is universally equivalent to a 2-dimensional one.
