A set of circles would generate the smallest "edge length". But, it would leave a a lot of space between them. :-)
For adjacent figures (or districts), squares would yield the smallest overall edge length. But, you'd still have the problem with political boundaries -- which is why I proposed the exceptions.
There is a way to specify this algorithmically: a good mathematician would be able to do it, and apply it to the 2010 census data (voting age population only -- no other factors should be allowed).
THEN, someone could test it against recent vote tabulations to predict the probable outcomes and identify the contested districts. It would be really interesting to compare it to the results of the inevitable gerrymandering.
This would be an great research project. I wonder if anyone would be willing to undertake it and publish the results?
So something like.....
Start at the state capital building, and draw a ring of concentric circles at 1 mile intervals. If the number of residents / voters inside that circle is less than some target, proceed to the next +1 mile radius. Keep doing so till you reach a max number of voters.
You could then divide the rings along N, S, E, W and likewise, continue with the rings.
You could use squares or rectangles as well but they would require greater description.