Partitioning a connected shape into rectangles
David Eppstein gave an excellent answer for this question here on MathOverflow (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.