Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

I beg your pardon for my bad drawings

enter image description here

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)


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?

share|cite|improve this question
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

@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$.

share|cite|improve this answer

"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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.