# Grids and Graphs

1. Jun 3, 2007

### birulami

Consider a rectangular grid on a piece of paper. It represents a graph where every node has 4 neighbours (except at the border, but just imagine the graph extended indefinitely). When stacking and arranging cubes, the edges of the cubes make a graph where every node has exactly 6 neighbours.

Similarly consider the middle of the rectangles of the grid as graph nodes and consider the diagonal neighbours too. Then in the graph each node has exactly 8 neighbours. In the cubes case, we arrive at 26 neighbours.

Afaik there is only a small finite number of ways to tile the 2D plane regularly as with a rectangular grid (hexagons and triangles would work too), so in graphs derived from theses geometric constructions, the number of neighbours is restricted.

Apart from every node having exactly the same number of neighbours, there is something more that characterizes these graphs, because in an infinite binary tree, for example, each node has exactly three neighbours, but the tree obviously has no loops. Now I have several questions:

a) How can we characterize these grid-derived graphs in a geometry-free definition? It could start with the fixed number of neighbours. Another property might be that all neighbours of a node form a loop. Anything else?

b) Is it possible to have any N as the fixed number of neighbours or will it turn out that every satisfying characterization (whatever satisfying is, if I knew I would not ask) points back to a grid and therefore restricts the possible N and even binds them to a dimension of the grid?

c) If every N is possible, can we nevertheless define a "dimension" purely graph theoretic such that when a map back to a grid is possible, the dimensions match?

Thanks,
Harald.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted