# What kind of graph is this?

I have a 2D grid of arbitrary positive integer points, minimum being $0,0$ to a maximum of $n,n$. I can only traverse points by increasing my $x$ and/or $y$ coordinate (no backtracking).

Is this sort of data structure a directed acyclic graph? If so, how can I "convert" it to "linear" sequence form?

• Can you clarify, what do you mean by "convert it to linear sequence form"? What are you trying to calculate? – Calvin Lin Jan 20 '13 at 16:45
• @CalvinLin So I can convert it to a 1D array representation – MyNameIsKhan Jan 20 '13 at 16:54

I am not sure if I get your question but here it is. The graph is a directed acyclic graph with $n^2$ vertices.

If you label each cell $(i, j)$ of the grid with $in + j \ \textit{mod} \ n$ then you can create a 1d array to represent the graph where the $k$-th index represents the $k$-th vertex. From position $k$ you can go to position $k + 1$ if $k < n - 1$ and $k + n$ if $k < (n - 1)n$.

But you still need $n^2$ positions so I don't understand what you want to do exactly. If you can be clearer then maybe I can help more.

• I have a grid of size n by n. I have points on this grid (arbitrary number / position of them). I can only go from one point to another, and I can only go to an immediately visible point that is greater than the one I am currently at in either x, y, or both x and y coordinate. – MyNameIsKhan Jan 20 '13 at 17:42

First, as has been mentioned, this is a directed acyclic graph. It sounds like your "linear sequence form" is an arrangement of the vertices in a left-to-right sequence $\langle v_1, v_2, \dots , v_n\rangle$ such that any edge goes from left to right in the sequence. If so, you're asking for what's commonly known as a topological sort of the vertices.

For your graphs an easy way to do this is to order the vertices first by weight, where the weight of a vertex $w(i, j)=i+j$ and then within each weight order the vertices by their first coordinate. For example, if $n=2$ we'll have the linear order $$(0,0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2)$$ Now look at the edges. From $(i, j)$ we'll have edges to $(i+1, j), (i, j+1), (i+1, j+1)$, as long as $i+1\le n$ and $j+1\le n$. Each of these edges will have weight strictly greater than $i+j$ so each of the edges from $(i, j)$ will end at a vertex of greater weight, hence to the right of $(i, j)$. This also shows that the graph is acyclic.

Notice that there are other ways of arranging the vertices in a line (simply permute the edges of equal weights).