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.
KaryTree[31, 2]
except with the root node branching out into 3 instead of 2. Each node has 3 neighbours, except the leaves (the boundary). Is this an acceptable solution? If not, why not? $\endgroup$ – Szabolcs Jul 9 '15 at 8:11GraphPeriphery
function, which by definition doesn't actually return the intuitive boundary under consideration, for example in the case of aGridGraph
in general. But what the intuitive "boundary" of such regular planar graphs should be actually called? $\endgroup$ – kirma Jul 10 '15 at 9:36