Krieger's embedding theorem for $\mathbb{Z}$ mixing shifts for finite type (SFTs) is extended to the $\mathbb{Z}^2$ case. We prove that if X is a non-periodic subshift ($\sigma^vx=x\Rightarrow v=0\in\mathbb{Z}^2$) and Y is a $\mathbb{Z}^2$ square-filling mixing SFT, then there exists a homomorphism $X\to Y$. The proof is a construction which begins by constructing Voronoi tilings using techniques from Part I (S. Lightwood. Morphisms from non-periodic $\mathbb{Z}^2$ subshifts I: constructing embeddings from homomorphisms. Ergod. Th. & Dynam. Sys.23 (2003), 587–609.). A tiling by Delaunay polygons is derived from Voronoi tiling. The union of the boundaries of the Delaunay polygons (referred to as the Delaunay graph) is itself tiled by trees. Words painted on the thickened trees combine to form words on the thickened infinite Delaunay graph. It is the point and sole purpose of square-filling that words on such thickened infinite graphs will correspond to points in the target space.

Combined with the results from Part I, this gives us the $\mathbb{Z}^2$ extension of Krieger's Embedding Theorem: if X is a non-periodic subshift and Y is a $\mathbb{Z}^2$ square-filling mixing SFT, then there exists an embedding $X\hookrightarrow Y$ if and only if $h(X)<h(Y)$, where h denotes the $\mathbb{Z}^2$ entropy. The techniques developed here play a central role in the proof of an embedding theorem for general $\mathbb{Z}^2$ subshifts into square-filling mixing SFTs which will be carried out in a subsequent paper.