# Cell-adjacency Graph of a Square Mesh

Consider the list of points

pts = {{1, 1}, {1, 2}, {2, 1}, {2, 2}}


I want to use them to define a 2x2 square mesh using VoronoiMesh, where each cell has two neighbours. Following the discussion in this question, consider the following code

mesh = VoronoiMesh[pts, ImageSize -> Medium];
conn = mesh["ConnectivityMatrix"[2, 1]];
centers = PropertyValue[{mesh, 2}, MeshCellCentroid];
VertexCoordinates -> centers];
Show[mesh, g] As one can see, unlike other meshes, this one does not seem to work exactly as I want, since the diagonal edge should not appear. Why is this happening? Any way of avoiding that edge and get as one would expect from a square lattice?

Edit: As noticed in the comment section, some of the polygons seem to have sharing edges that are single points, which is enough for them to be considered neighbouring cells. This effect is unchanged with the size of the lattice. If I consider, for example, the points

pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1];


I get Any ideas on how to solve this? Maybe omit the extra edge in a way that doesn't this or other non-square meshes. For example, considering a random VoronoiMesh, nothing seems to wrong, though it could, theoretically, go • Something somewhat strange... faces 3 and 4 have 5 sides: In:= MeshCells[mesh, 2] Out= {Polygon[{4, 1, 3, 6}], Polygon[{5, 1, 2, 9}], Polygon[{7, 3, 1, 1, 5}], Polygon[{8, 2, 1, 1, 4}]}. But notice 1 is repeated twice...so structurally they share an edge, but that 'edge' is really just a point. – Chip Hurst Jan 15 at 21:57
• That's right. Would it be possible to delete that 1 in a reasonably natural manner? So that it wouldn't affect other possible meshes? – sam wolfe Jan 15 at 22:07
• The problem persists with bigger lattices. Please see edit section. – sam wolfe Jan 15 at 22:22
• IGraph/M handles this well. Did you try it? IGMeshCellAdjacencyGraph[mesh, 2]. You may also want to add VertexCoordinates -> Automatic – Szabolcs Jan 15 at 22:26
• Well, it's open-source so you can check ... It's based on Henrik's answer in the linked question. – Szabolcs Jan 16 at 8:05

We can delete the rows in our incidence matrix that correspond to these edges of length 0.

pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1];

mesh = VoronoiMesh[pts, ImageSize -> Medium];
conn = mesh["ConnectivityMatrix"[1, 2]];

lens = PropertyValue[{mesh, 1}, MeshCellMeasure];
$$threshold = 0.; keep = Pick[Range[MeshCellCount[mesh, 1]], UnitStep[Subtract[$$threshold, lens]], 0];
conn = conn[[keep]];

centers = PropertyValue[{mesh, 2}, MeshCellCentroid];

Show[mesh, g] You can delete the unwanted edges using EdgeDelete:

Show[mesh, EdgeDelete[g, UndirectedEdge[a_, b_] /;
(FreeQ[Chop[Differences[PropertyValue[{g, #}, VertexCoordinates] & /@ {a, b}]]])]] For g generated using pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1]; we get L1 = 2; L2 = 2;
mesh = VoronoiMesh @ Tuples[Range /@ {L1, L2}];
centers = Rationalize @ PropertyValue[{mesh, 2}, MeshCellCentroid];

g1 = VertexReplace[GridGraph[{L2, L1}, PlotTheme -> "Scientific",
VertexCoordinates -> centers[[Ordering @ centers]],
{v_ :> Ordering[centers][[v]]}];

Show[mesh, g1] For L1 = 7; L2 = 5; the same approach gives 