The webpage http://what-if.xkcd.com/113 explores the fewest number of lines needed so that every state in the US has at least one line going through it. (actuallly great circles on a sphere)
Can you provide references that study questions of the following types:
The lines must properly pass through each region not just their boundaries. Contiguous regions must share a boundary not just a single point.
Given an area divided into contiguous regions, what is an efficient method to minimize the number of lines needed so that every region has at least one line going through it? How to find and prove the minimal number?
For the integer $n$, how to draw $n$ contiguous regions so as to maximize the number of lines needed and what is the maximum number? (after a bit of thought I think any three contiguous regions can be connected by a single line, so no more than $n/3 +1$ lines would be needed but is there a better bound? perhaps $\sqrt(n)$?
Or if there are no references, can you answer them?