<p>Consider this variation: we want to find number of paths which goes from $(1,1)-&gt;(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.</p>

CC BY-SA 3.0
2014-04-02T14:17:15.947Z
2014-04-02T14:17:15.947Z
Saeed
<p>Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$.
Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on the number of simple $st$-path using those edges.</p>

<p>If I see  the grid as a box in the plane, I can visualize an $st$-path as a rectilinear curve cutting this box. In this way I can associate each cell of the grid to either one or the other partition, getting as a trivial upper bound the value of $2^{n^2}$.
Is there any better?</p>

<p>I also thought that, if I am considering only the paths using the $k$ given edges on the upper line, then I can map each of these paths to a cut of the grid graph into $k+1$ partitions.
Do you know whether any non-trivial upper bound on this number is known?</p>

<p>Thanks for the help!</p>

<graph-theory><planar-graphs><upper-bounds>
Number of $k$-cuts of grid graphs
user22350
# Number of $k$-cuts of grid graphs

(Asked by: username_0 on 2014-04-02)

Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$.
Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on the number of simple $st$-path using those edges.

If I see the grid as a box in the plane, I can visualize an $st$-path as a rectilinear curve cutting this box. In this way I can associate each cell of the grid to either one or the other partition, getting as a trivial upper bound the value of $2^{n^2}$.
Is there any better?

I also thought that, if I am considering only the paths using the $k$ given edges on the upper line, then I can map each of these paths to a cut of the grid graph into $k+1$ partitions.
Do you know whether any non-trivial upper bound on this number is known?

Thanks for the help!

**Tags:** graph-theory, planar-graphs, upper-bounds


---

## 1 answers

### Answer by username_1 on 2014-04-02. Score: 0 | Accepted answer

Consider this variation: we want to find number of paths which goes from $(1,1)->(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.


---

