# What graph is this?

For my game I am trying to implement a continues world by interconnecting the nodes like below

I don't know how to explain it but its NOT DENSE GRAPH

It is representation of 3x3 nodes Where every node is connected to adjacent node vertically or diagonally (edges in turquoise color)

Ex:

1-2, 1-4 2-1,2-3,2-5 5-2, 5-6, 5-4, 5-8

Now there are some edges (colored in blue and purple)

1-7, 1-3 4-6 2-8

I need edges like this for creating endless/continues world for my game

My world is actually lot bigger than this but I made 3x3 for the sake of drawing.

Is there any name for this type of graph?

-
Every node isn't connected to adjacent node in the graph you shown. Torodial graph is the closes to what your describing. – simplicity Feb 23 '13 at 9:44
Also, you should post on gamedev stackexchange. – simplicity Feb 23 '13 at 9:51
Isn't this a cartesian product of cycles? – Johannes Kloos Feb 23 '13 at 9:56
It's a torodial graph. A graph that can be embedded into a torus. A torus is a cartesian product of cycles. – simplicity Feb 23 '13 at 9:57
This graph isn't like a globe. It's like the surface of a donut. – MartianInvader Feb 25 '13 at 17:35

"Where every node is connected to adjacent node vertically or diagonally"

Judging from the picture, it should say horizontally instead of diagonally. And if the vertices are connected to every vertex vertically and horizontally, fidbc's answer is correct for the $3 \times 3$ case, but not in general.

If the above is correct, this graph is known as the $3 \times 3$ rook's graph. Generalising this to the $k \times n$ case, it is the Cartesian product of $K_k$ and $K_n$, and the line graph of the complete bipartite graph $K_{k,n}$.

If $n \geq k$, then the number of $n$-colourings of of the $k \times n$ rook's graph is the number of Latin rectangles of order $n$. In particular, the number of $n$-colourings of of the $n \times n$ rook's graph is the number of Latin squares of order $n$. Further, the chromatic polynomial of this graph counts a generalisation of Latin rectangles.

I discuss this graph in my survey paper The Many Formulae for the Number of Latin Rectangles.

-

@Johannes Kloos is right. The graph in the picture is just the cartesian product of $C_3$ with itself. I think in general you are interested in the cartesian product of $C_k$ and $C_l$.

-