  For given a pair of nodes in a graph, the minimum non-separating path problem
looks for a minimum weight path between the two nodes such that the remaining
graph after removing the path is still connected. The balanced connected
bipartition (BCP$_2$) problem looks for a way to bipartition a graph into two
connected subgraphs with their weights as equal as possible. In this paper we
present an algorithm in time $O(N\log N)$ for finding a minimum weight
non-separating path between two given nodes in a grid graph of $N$ nodes with
positive weight. This result leads to a 5/4-approximation algorithm for the
BCP$_2$ problem on grid graphs, which is the currently best ratio achieved in
polynomial time. We also developed an exact algorithm for the BCP$_2$ problem
on grid graphs. Based on the exact algorithm and a rounding technique, we show
an approximation scheme, which is a fully polynomial time approximation scheme
for fixed number of rows.
