Arbitrary shape GridGraph

Question

There is a function GridGraph that generates a finite square lattice graph. Is there a way to make a generalized solution (e.g. with hexagons, or triangles instead of squares)?

To put it in more strict form, I need a subgraph of a finite lattice where each vertex have exactly n neighbors, except a set of "boudary vertices" B. Vertices from B can will have less than n adjacent edges. One can think of boundary vertices as a periphery of the graph.

As you can see from my explanation, I have some difficulties with strict mathematical description of my problem, and I think this is why I am struggling so much trying to solve it. Here is what I've tried so far:

• NestList, where on each step I am taking one of the boundary vertices bv and adding a few vertices, so that bv is not in the periphery anymore, and new vertices are taking its place. I've realized that it this approach is dependent in a way I am selecting vertices from the periphery and extremely sensitive to a starting graph.

• Generating coordinates for a vertices in $R^2$, and then building a Unit Disk Graph. This was an interesting experiment by itself, however, I wasn't able to provide an algo for putting points in the right places.

• Randomly connecting vertices in a graph with no edges while their power is less than n. Obviously, I've got crazy graphs that were not even close to a regular lattice.

There is a solution for hex grid, that could be used together with a unit disk graph method described above.

Answer 1

Admittedly the implementation below is not as simple or efficient as I wished. Some of the visualizations are a bit messy, but I think it works correctly.

Basically it tracks the planar graph boundary and tries to add new edges in regularity-admitting locations. Regular planar tilings are trivially present, but this code also generates Platonic graphs corresponding to regular Platonic polyhedra (these close on themselves, and don't have a "boundary"), and graphs corresponding to tilings in hyperbolic geometry.

Module[{regularGraphBoundary, takeClosestVertexGroup, 
  selectAdmissableArcs, addNewEdges, tryAddPolygon},
 regularGraphBoundary[g_Graph, nvertices_Integer] :=
  Graph[First /@
    Select[Tally[Sort /@ Flatten@FindCycle[g, {nvertices}, All]], 
     Last@# == 1 &]];

 takeClosestVertexGroup[g_Graph, groups_List] :=
  First@TakeSmallestBy[
    groups, Min[GraphDistance[g, 1, #] & /@ #] &, 1];

 selectAdmissableArcs[g_Graph, candidates_List, nvertices_Integer, 
   targetdegree_Integer] :=
  Select[
   candidates,
   VertexDegree[g, First@#] < targetdegree &&
     And @@ (VertexDegree[g, #] == targetdegree & /@ #[[2 ;; -2]]) && 
     VertexDegree[g, Last@#] < targetdegree &];

 addNewEdges[g_Graph, oldvertices_List, nvertices_Integer] :=
  GraphUnion[g,
   Graph[UndirectedEdge @@@
     Partition[{First@oldvertices,
       Sequence @@ (Unique[] & /@ 
          Range[nvertices - Length@oldvertices]),
       Last@oldvertices},
      2, 1]]];

 tryAddPolygon[g_Graph, vertices_Integer, targetdegree_Integer] :=
  Module[{graphboundary, admissablearcgroups},
   graphboundary = regularGraphBoundary[g, vertices];

   If[EmptyGraphQ@graphboundary,
    g,

    admissablearcgroups =
     Flatten[
      Table[
       selectAdmissableArcs[g, 
        Partition[First /@ First@FindCycle@graphboundary, n, 1, 1],
        vertices, targetdegree],
       {n, vertices, 2, -1}],
      1];

    addNewEdges[
     g, takeClosestVertexGroup[g, admissablearcgroups], vertices]]];

 Grid[Table[
   HighlightGraph[#, regularGraphBoundary[#, v]] &@
    Nest[tryAddPolygon[#, v, d] &, CycleGraph[v], 150], {v, 3, 7}, {d, 
    3, 7}], Frame -> All]]

Answer 2

IGraph/M now has some new lattice graph generation features that might be useful (though not every graph of the type you describe can be generated through these functions).

Here's a demo through a few examples:

IGTriangularLattice[5]

IGTriangularLattice[{4, 5}]

IGBetheLattice[5]

There is IGLatticeMesh which uses (a post-processed version of) Mathematica's built-in periodic tiling data to generate various meshes. These can be converted to graphs using IGMeshGraph, or to face-face adjacency graphs (i.e. the dual) using IGMeshCellAdjacencyGraph[mesh, 2, VertexCoordinates -> Automatic].

IGLatticeMesh["Hexagonal"]

IGLatticeMesh["Hexagonal", {3, 2}]

IGLatticeMesh["Hexagonal", Polygon@CirclePoints[4, 6]]

IGLatticeMesh["Trihexagonal"]

Convert to graphs:

IGMeshGraph[%]

IGMeshCellAdjacencyGraph[%%, 2, VertexCoordinates -> Automatic]

In this last graph, not all non-boundary vertices have the same number of neighbours. I included it as an illustration of how to extract the dual lattice, which may be useful for some other tilings.