Minimum number of cuts to divide a rectangle
Each edge of an inner rectangle that (that isn't on the exterior of the big rectangle) is a line segment.  Your problem now becomes: given a collection of line segments, find the minimum number of lines to cover all of the line segments (and nothing more).

This problem can be solved as follows.  For each line segment, extend the line as far as you can in both directions, until it no longer is touching any line segment.  Add that line to your collection of lines.  Repeat until you've covered all of the line segments.  In other words, merge two line segments if they are touching and go in the same direction (since in that case they can be merged into a single line that covers both).  Repeat until you can't merge anything any longer.