Census Dual Graphs: Properties and Random Graph Models
For researchers in computational redistricting, this paper provides the first systematic characterization of dual graph properties and validates random graph models, enabling more realistic simulations and algorithm testing.
This paper characterizes the properties of dual graphs used in political redistricting, analyzing real dual graphs from U.S. counties and census units, and identifies random graph models (e.g., perturbed grids, Delaunay triangulations) that best match key metrics. The work provides a foundational understanding of this graph class for algorithm development.
In the computational study of political redistricting, feasibility necessitates the use of a discretization of regions such as states, counties, and towns. In nearly all cases, researchers use a dual graph, whose vertices represent small geographic units (such as census blocks or voting precincts) with edges for geographic adjacency. A political districting plan is a partition of this graph into connected subgraphs that satisfy certain additional properties, such as connectedness, compactness, and equal population. Though dual graphs underlie nearly all computational studies of political redistricting, little is known about their properties. This is a unique graph class that has been described colloquially as `nearly planar, nearly triangulated,' but thus far there has been a lack of evidence to support this description. In this paper we study dual graphs for counties, census tracts, and census block groups across the United States in order to understand and characterize this graph class. We also consider several random graph models (most based on randomly perturbing grids or Delauney triangulations of random point sets), and determine which most closely resemble dual graphs under key metrics. This work lays an initial foundation for understanding and modeling the properties of dual graphs; this will provide invaluable insight to researchers developing algorithms using them to understand, assess, and quantify the properties of political districting plans.