The "graph partitioning" problem is NP-complete: problem ND14 in Garey & Johnson: Comnputers and Intractibility, a guide to the theory of NP completeness, freeman 1978.
Thus even if the country is to be divided into only 2 districts we have NP-hardness. It is conceivable this could be escaped because we have a planar graph not a general graph. A polynomial time algorithm to find an APPROXIMATE grpah partitioning for a planr graph, is T. N. Bui and A. Peck. Partitioning planar graphs. SIAM J. on Computing, 21(2):203-- 215, 1992. But their algorithm is exponential time if you make the aprpoximation too good. http://locus.siam.org/SICOMP/volume-21/art_0221016.html See also even worse news showing APX-completeness Chlebikova, J. (1996), ``Approximability of the Maximally balanced connected partition problem in graphs'', Inform. Process. Lett. 60, 225-230. but again this is about general graphs. For planar graphs it remains conceiveable there is a polytime algorithm but I doubt it. I think it will be shown NP-complete some day, and I also think this is even more likely if the number of districts exceeds 2. wds ---- Election-methods mailing list - see http://electorama.com/em for list info
