Connecting a $n, n$ point grid

I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen.

For $n=1, n=2$ it is trivial. For $n=3$ you can find the solution with a bit trial and error (I will leave this to the reader as it is a fun to do, you can do it with 4 lines). I found one possible solution for a $4,4$ grid and animated it, it uses 6 lines and is probably optimal (will hopefully help you to understand the problem better, the path doesn't have to be closed like in the animation, open ends are allowed!):

Now my question is, for higher $n$, is there a way to get the amount of minimal lines to use and does an algorithm exist to find a actual solution? I think its quite hard to model the "straight lines" with graph theory.

Edit: Reading Erics excellent answer I found the following website: http://www.mathpuzzle.com/dots.html that also gives an algorithm to connect the points in $2n-2$ steps, solutions up to $10,10$ and mentions:

Toshi Kato conjectures: On $(2N+1)x(2N+1)$ grid, $N \geq 2$, Using $4N$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N+1)x(2N+1)$ grid, ending at the same place started. But must visit at least one dot twice in the route.

On $(2N)x(2N)$ grid, $N \geq 2$, Using $4N-2$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N)x(2N)$ grid, ending at the same place started. And can visit each dots just once.

It seems to be an open problem to show that $2n-2$ is optimal.

Also I found the following page with a proof that in the $3,3$ grid there cannot be $2$ parallel lines: http://fahim-patel.blogspot.com/2011/01/proof.html I think it might be interesting for coming up with a proof that $2n-2$ is optimal (however maybe there is no such proof, as we only saw solutions for very small $n$, for bigger $n$ there might be some developments we don't know about).

Interesting question. In what follows consider the $n\times n$ square grid. Notice that the trivial solution obtained by following a square spiral towards the center starting from an outside corner yields a solution with $2n-1$ lines.
To see why, notice that 2 lines reduces the grid to a $(n-1)\times (n-1)$ grid, and since the $1\times 1$ grid requires only 1 line, induction yields $2n-1$ lines.

Can we do better? Based on the posts in the forum and my own attempts, I believe the answer is that $2n-2$ lines is optimal. Showing this is possible is again easy. Start at a corner, and spiral towards the center until there is only a $3\times 3$ grid remaining. Recall from above that 2 lines in the spiral will reduce the grid by a dimension, so thus far we will have used $2\cdot (n-3)=2n-6$ lines. On the last line, end it so that we are in a position to go through the diagonal of the $3\times 3 $ grid. Since the $3\times 3$ grid has a solution with $4$ lines starting diagonally from a corner we have found a solution to the $n\times n$ grid using only $2n-2$ lines.

Now, the question remains, is $2n-2$ optimal? The more I think about it, the more I believe it, but a proof does not leap into mind. I will think more.

Edit: Of course $n=1,2$ are exceptions, and required $2n-1$ lines. The method I presented can be modified slightly to produce a closed path. All that must be changed is the way the final $3\times 3$ grid is traversed, and perhaps moving the starting position of the first line to a spot slightly outside of the original $n\times n$ grid. In other words the conjecture Toshi Kato is true.

Edit 2: For a proof that $2n-2$ is optimal, see Joriki's answer to this question Not lifting your pen on the $n\times n$ grid.

There is some discussion of this problem here: http://www.tek-tips.com/viewthread.cfm?qid=1370890&page=2