Redrawing congressional districts in the United States is a constitutionally required, yet politically controversial, task undertaken after each decennial census. Federal law requires contiguous, `relatively compact' congressional districts that maintain `approximately equal' population. Controversy is introduced when individual states redraw their districts, or redistrict, using partisan committees. States such as Ohio continue to redistrict with a committee appointed according to the current proportion of legislators' political parties to the whole. When political parties have majority power in redistricting committees, they can draw districts in a way that gives their party the best chance to keep its majority representation, a process called gerrymandering. Mathematical redistricting models seek an unbiased computational approach to the problem. Rather than trust partisan committees, mathematical modeling approaches rely upon well-defined methods in computational geometry, graph theory, game theory, and other fields. Here, we discuss two such approaches. The first, given as a background for comparison, constructs Voronoi diagrams to redistrict states into convex polygons, which are generally considered `compact'. We give greater emphasis to a new model that discretizes a state's population and partitions it into regions of approximately equal population. This model, our main focus, relies upon graph partitioning to achieve the desired result and uses census population data as the sole parameter in redistricting.
"A Graph Partitioning Model of Congressional Redistricting,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 16:
2, Article 3.
Available at: https://scholar.rose-hulman.edu/rhumj/vol16/iss2/3