Extending the 9 dots problem

The 9 dots problem asks you to connect all the dots using just 4 lines, without lifting your pencil:

Most people are surprised by the solution, pictured below:

Because we're given a 3x3 grid of dots, a natural question arises: How many lines are necessary for a 4x4 grid? Is there a nice strategy that works in general, or a nice formula that gives the number of lines necessary for a wxh grid? Certainly we can find a lower bound for the number of lines, by starting at a corner and spiralling towards the center. What about rectangular grids? Here's a solution for the 4x3 variant of the puzzle:

And here's a solution for the 6x6 variant:

After playing with this problem for a while, when you're ready for some answers, I recommend reading this very interesting paper, in which the authors attempt to bound the minimum and maximum number of lines, both for nxn grids, and nxnxn grids. One of the authors has also posted a video showing the solution for a 3x3x3 grid.

I also wonder if this problem might be applied to other lattices, such as triangular, tetrahedral, or hexagonal lattices.