Geo-Graphs: An Efficient Model for Enforcing Contiguity and Hole Constraints in Planar Graph Partitioning

Douglas M. King (), Sheldon H. Jacobson (), Edward C. Sewell () and Wendy K. Tam Cho ()
Additional contact information
Douglas M. King: Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana, Illinois 61801
Sheldon H. Jacobson: Department of Computer Science, University of Illinois, Urbana, Illinois 61801
Edward C. Sewell: Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, Illinois 62026
Wendy K. Tam Cho: Department of Political Science and Statistics, National Center for Supercomputing Applications, University of Illinois, Urbana, Illinois 61801

Operations Research, 2012, vol. 60, issue 5, 1213-1228

Abstract: Political districting is an intractable problem with significant ramifications for political representation. Districts often are required to satisfy some legal constraints, but these typically are not very restrictive, allowing decision makers to influence the composition of these districts without violating relevant laws. For example, while districts must often comprise a single contiguous area, a vast collection of acceptable solutions (i.e., sets of districts) remains. Choosing the best set of districts from this collection can be treated as a (planar) graph partitioning problem. When districts must be contiguous, successfully solving this problem requires an efficient computational method for evaluating contiguity constraints; common methods for assessing contiguity can require significant computation as the problem size grows. This paper introduces the geo-graph , a new graph model that ameliorates the computational burdens associated with enforcing contiguity constraints in planar graph partitioning when each vertex corresponds to a particular region of the plane. Through planar graph duality, the geo-graph provides a scale-invariant method for enforcing contiguity constraints in local search. Furthermore, geo-graphs allow district holes (which typically are considered undesirable) to be rigorously and efficiently integrated into the partitioning process.

Keywords: graphs/theory; plane graph partitioning; government/elections; political districting; graphs/heuristics; local search (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1083 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:5:p:1213-1228

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().