arxiv: 2604.04960 · v1 · submitted 2026-04-03 · 💻 cs.DM · math.CO

Recognition: no theorem link

Census Dual Graphs: Properties and Random Graph Models

Anne Friedman, Brooke Feinberg, Sara Anderson, Sarah Cannon

Authors on Pith no claims yet

Pith reviewed 2026-05-13 18:01 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords dual graphscensus dataredistrictingplanar graphstriangulationsrandom graph modelsgraph propertiesadjacency graphs

0 comments

The pith

US census dual graphs are nearly planar and nearly triangulated, with perturbed grids and Delaunay triangulations as the closest random models.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Researchers in political redistricting build algorithms on dual graphs whose vertices represent small geographic units such as counties or census blocks and whose edges connect units that share a border. This paper measures the structural properties of these graphs for counties, census tracts, and block groups across the entire United States. The graphs turn out to be consistently close to planar, with few crossings, and close to triangulated, with most faces being triangles. The authors generate several families of random graphs and compare them on the same properties, finding that models formed by slightly moving the points of a regular grid or by connecting random points into a Delaunay triangulation reproduce the real graphs most accurately on planarity, triangle count, and degree statistics.

Core claim

The dual graphs constructed from US census geographies for counties, census tracts, and block groups are nearly planar and nearly triangulated. Among random graph models considered, those obtained by perturbing grid points or by taking Delaunay triangulations of random point sets most closely match the real dual graphs in terms of planarity, number of triangles, degree sequences, and other metrics.

What carries the argument

The dual graph of geographic adjacency for census units, evaluated for near-planarity and near-triangulation, and matched to synthetic models including perturbed grids and Delaunay triangulations.

If this is right

Redistricting algorithms can be tested and tuned on the identified random models to predict behavior on actual US census instances.
The near-triangulation property limits the number of possible compact district shapes that satisfy adjacency constraints.
Synthetic instances generated from the best-matching models can serve as benchmarks for comparing different districting methods at scale.
The characterization supplies a starting point for proving theoretical guarantees about algorithms that operate on this specific class of graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the measured metrics correlate with running time, the same random models could be used to study the computational complexity of redistricting problems.
The same measurement approach could be applied to dual graphs built from voter precincts or from administrative units in other countries.
One could check whether the observed near-planarity implies low treewidth or other algorithmic properties that would allow faster exact solvers.
Dynamic versions of these graphs that update after each census could be modeled by adding or removing vertices in the same perturbed-grid style.

Load-bearing premise

That the chosen graph metrics such as planarity, triangulation density, and degree sequences are the ones that matter most for how redistricting algorithms will perform on these graphs.

What would settle it

A measurement showing that a substantial fraction of real census dual graphs require many crossings in any drawing or that a different random model matches the observed planarity and triangle counts more closely than the perturbed-grid and Delaunay models.

Figures

Figures reproduced from arXiv: 2604.04960 by Anne Friedman, Brooke Feinberg, Sara Anderson, Sarah Cannon.

**Figure 1.** Figure 1: A plot showing ln(NST (G)) vs. |V (G)| for all connected census tract and block group graphs Dual graphs of geographic maps are often planar, since they are derived from non-overlapping spatial regions. However, in practice, certain geographic features, such as adjacencies across bodies of water or boundary points where multiple regions meet, can result in non-planar graphs. We also found that nearly three… view at source ↗

**Figure 2.** Figure 2: Spanning tree constant for census tract and block group dual graphs [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: For the Oregon counties dual graph, a spanning tree that can be split into two balanced [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: Logarithmic transformation of county data, with regression line log( [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

**Figure 5.** Figure 5: Logarithmic transformation of tract data, with regression line log( [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 6.** Figure 6: Logarithmic transformation of block group data, with regression line log( [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

**Figure 7.** Figure 7: Logarithmic transformation of county data, with overall regression line log( [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗

**Figure 8.** Figure 8: Logarithmic transformation of tract data, with overall regression line log( [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗

**Figure 9.** Figure 9: Logarithmic transformation of county data, with overall regression line log( [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗

**Figure 10.** Figure 10: Examples of Square and Triangular grid graphs [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗

**Figure 11.** Figure 11: Computed spanning tree constants vs. number of vertices for dual graphs (red, middle), [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗

**Figure 12.** Figure 12: Randomly perturbed grids with probabilities [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗

**Figure 13.** Figure 13: Compare spanning tree constant for real data to perturbing grid with probability [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗

**Figure 14.** Figure 14: A comparison of the spanning tree constant vs. number of nodes for real data (blue) [PITH_FULL_IMAGE:figures/full_fig_p019_14.png] view at source ↗

**Figure 15.** Figure 15: Visualizing three different random instances of Model 11c with 100 vertices [PITH_FULL_IMAGE:figures/full_fig_p019_15.png] view at source ↗

**Figure 16.** Figure 16: Example of a Delaunay triangulation of a point set with 15 points [PITH_FULL_IMAGE:figures/full_fig_p020_16.png] view at source ↗

**Figure 17.** Figure 17: Compare spanning tree constant for real data to Model 8 results [PITH_FULL_IMAGE:figures/full_fig_p022_17.png] view at source ↗

**Figure 18.** Figure 18: Visualizing three different random instances of Model 8 with 100 vertices [PITH_FULL_IMAGE:figures/full_fig_p022_18.png] view at source ↗

**Figure 19.** Figure 19: Comparing the spanning tree constant for real data to Model 8 and Model 12 results [PITH_FULL_IMAGE:figures/full_fig_p023_19.png] view at source ↗

**Figure 20.** Figure 20: Visualizing three different random examples of Model 12 with 100 vertices [PITH_FULL_IMAGE:figures/full_fig_p024_20.png] view at source ↗

**Figure 21.** Figure 21: Comparing average degree and average spanning tree constant results for the most [PITH_FULL_IMAGE:figures/full_fig_p026_21.png] view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Census dual graphs match the nearly planar and triangulated description, with perturbed grid and Delaunay models performing best in comparisons.

read the letter

This paper's main contribution is showing that dual graphs built from US census data really are nearly planar and nearly triangulated, with the first set of measurements across counties, tracts, and block groups. It also tests random graph models and finds that perturbed grids and Delaunay triangulations of random points come closest to the real structures. The work is new because it replaces the usual hand-waving about these graphs with actual numbers on planarity, triangulation density, degree sequences, and other invariants. The authors generate several families of random models, including ones based on grid perturbations and random point sets, then compare them directly to the empirical graphs. This gives a foundation for creating synthetic versions that researchers can use when testing redistricting algorithms. The paper does the comparison in a straightforward way. It identifies which models match best under the chosen metrics, which is helpful for anyone who needs realistic test graphs without pulling real census boundaries. The approach is empirical and avoids any circular fitting since the models are built independently of the target data. The soft spots are minor. The metrics are the natural ones for graph structure, but they may not be the most predictive for how redistricting algorithms actually behave on these graphs, like under compactness or population equality constraints. The strength of the resemblance would be clearer with explicit statistical comparisons or effect sizes, though the overall direction seems consistent. No load-bearing assumptions look shaky from the description. This is aimed at people working on computational redistricting and graph-based political analysis. Anyone building or validating algorithms on dual graphs will find the characterization and model suggestions practical. It deserves peer review because it provides the first solid data on a graph class that is used everywhere in the area but had almost no prior study.

Referee Report

0 major / 3 minor

Summary. The paper empirically characterizes dual graphs constructed from US census geographic units (counties, census tracts, and census block groups), providing quantitative support for the description that these graphs are nearly planar and nearly triangulated. It evaluates several random graph models, primarily those based on perturbed grids and Delaunay triangulations of random point sets, to determine which most closely match the real dual graphs under standard invariants including planarity testing, average degree, degree sequences, and triangulation density. The work positions these findings as a foundation for improved modeling in computational redistricting studies.

Significance. If the empirical comparisons hold under the reported metrics, the paper supplies the first systematic evidence for the structural properties of dual graphs that underpin nearly all redistricting algorithms. This descriptive characterization enables more faithful random models for algorithm testing and validation, directly addressing a recognized gap in the redistricting literature. The approach is appropriate for an initial characterization study and credits reproducible empirical methodology.

minor comments (3)

[Introduction] The abstract and introduction refer to 'key metrics' without an explicit list or justification in the provided text; a dedicated subsection enumerating the chosen invariants (planarity, triangulation density, degree sequence distance, etc.) and their relevance to redistricting would improve clarity.
[Random Graph Models] The perturbation scale parameter in the grid and Delaunay models is listed as a free parameter; the manuscript should report the specific values or ranges used in the experiments and any sensitivity analysis performed.
[Results] Figure captions and table legends would benefit from explicit statements of sample sizes (number of real dual graphs per category and number of random instances generated per model) to allow readers to assess statistical robustness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. The assessment correctly identifies the paper's focus on empirically characterizing census dual graphs as nearly planar and nearly triangulated, along with the evaluation of random models. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in empirical characterization

full rationale

The paper conducts an empirical study of real-world dual graphs derived from U.S. census data (counties, tracts, block groups) and compares their properties—planarity, triangulation density, degree sequences, etc.—against independently generated random graph models such as perturbed grids and Delaunay triangulations. No mathematical derivations, equations, or parameter-fitting steps are present that would reduce any claimed result to a definition or fit from the same data. The description of dual graphs as 'nearly planar, nearly triangulated' is treated as a colloquial observation to be tested, not a premise derived from the paper's own outputs. No self-citations are invoked as load-bearing justifications for uniqueness or ansatzes. The work remains self-contained as a descriptive comparison using standard graph invariants, with no reduction of predictions to inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard definition of dual graphs from geographic adjacency and on the assumption that the selected random-model families are appropriate baselines; no new entities are postulated.

free parameters (1)

perturbation scale in grid and Delaunay models
Random models require a tunable perturbation parameter whose value is chosen to match observed dual-graph statistics.

axioms (1)

domain assumption Geographic adjacency between census units defines the edges of the dual graph
Invoked in the opening paragraphs as the standard construction used in redistricting literature.

pith-pipeline@v0.9.0 · 5531 in / 1205 out tokens · 58394 ms · 2026-05-13T18:01:51.281331+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[1]

Geometry of graph partitions via optimal transport.SIAM Journal on Scientific Computing, 42(5):A3340–A3366, 2020

Tara Abrishami, Nestor Guillen, Parker Rule, Zachary Schutzman, Justin Solomon, Thomas Weighill, and Si Wu. Geometry of graph partitions via optimal transport.SIAM Journal on Scientific Computing, 42(5):A3340–A3366, 2020

work page 2020
[2]

Redistricting in triangular and square grids

Hugo Akitaya, Kyle Dituro, Andrei Gonczi, Matias Korman, Diane Souvaine, Frederick Stock, and Csaba D T´ oth. Redistricting in triangular and square grids. In2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 12–25. SIAM, 2026

work page 2026
[3]

Mattingly

Eric Autry, Daniel Carter, Gregory Herschlag, Zach Hunter, and Jonathan C. Mattingly. Metropolized forest recombination for Monte Carlo sampling of graph partitions.SIAM Jour- nal on Applied Mathematics, 83(4):1366–1391, 2023

work page 2023
[4]

Autry, Daniel Carter, Gregory Herschlag, Zach Hunter, and Jonathan C

Eric A. Autry, Daniel Carter, Gregory Herschlag, Zach Hunter, and Jonathan C. Mattingly. Metropolized multiscale forest recombination for redistricting.Multiscale Modeling & Simula- tion, 19(4):1885–1914, 2021

work page 1914
[5]

Computational redistricting and the voting rights act.Election Law Journal: Rules, Politics, and Policy, 20(4):407–441, 2021

Amariah Becker, Moon Duchin, Dara Gold, and Sam Hirsch. Computational redistricting and the voting rights act.Election Law Journal: Rules, Politics, and Policy, 20(4):407–441, 2021

work page 2021
[6]

Irreducibility of recombination Markov chains in the triangular lattice.Discrete Applied Mathematics, 347:75–130, 2024

Sarah Cannon. Irreducibility of recombination Markov chains in the triangular lattice.Discrete Applied Mathematics, 347:75–130, 2024

work page 2024
[7]

Spanning trees and redistrict- ing: New methods for sampling and validation

Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule. Spanning trees and redistrict- ing: New methods for sampling and validation. In press,SIAM Review, 2026

work page 2026
[8]

Sampling balanced forests of grids in polynomial time

Sarah Cannon, Wesley Pegden, and Jamie Tucker-Foltz. Sampling balanced forests of grids in polynomial time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024. 27

work page 2024
[9]

On the complexity of sampling redistricting plans

Moses Charikar, Paul Liu, Tianyu Liu, and Thuy-Duong Vuong. On the complexity of sampling redistricting plans. Preprint. Available athttps://arxiv.org/abs/2206.04883

work page arXiv
[10]

Stephanopoulos

Jowei Chen and Nicholas O. Stephanopoulos. The race-blind future of voting rights.The Yale Law Journal, 130(4), 2021

work page 2021
[11]

Dey, and Jonathan Shewchuk.Delaunay Mesh Generation, chap- ter 2

Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk.Delaunay Mesh Generation, chap- ter 2. Taylor & Francis Group, LLC, 1 edition, 2013

work page 2013
[12]

Separating effect from significance in Markov chain tests.Statistics and Public Policy, 7(1):101–114, 2020

Maria Chikina, Alan Frieze, Jonathan Mattingly, and Wesley Pegden. Separating effect from significance in Markov chain tests.Statistics and Public Policy, 7(1):101–114, 2020

work page 2020
[13]

Assessing significance in a Markov chain without mixing.Proceedings of the National Academy of Sciences, 114(11):2860–2864, 2017

Maria Chikina, Alan Frieze, and Wesley Pegden. Assessing significance in a Markov chain without mixing.Proceedings of the National Academy of Sciences, 114(11):2860–2864, 2017

work page 2017
[14]

Clelland, Nicholas Bossenbroek, Thomas Heckmaster, Adam Nelson, Peter Rock, and Jade VanAusdall

Jeanne N. Clelland, Nicholas Bossenbroek, Thomas Heckmaster, Adam Nelson, Peter Rock, and Jade VanAusdall. Compactness statistics for spanning tree recombination. Preprint. Available athttps://arxiv.org/abs/2103.02699, 2021

work page arXiv 2021
[15]

Census TopDown: The Impacts of Differential Privacy on Redistricting

Aloni Cohen, Moon Duchin, JN Matthews, and Bhushan Suwal. Census TopDown: The Impacts of Differential Privacy on Redistricting. In Katrina Ligett and Swati Gupta, editors, 2nd Symposium on Foundations of Responsible Computing (FORC 2021), volume 192 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:22, 2021

work page 2021
[16]

Introduction to discrete markov chain monte carlo for redistricting, June 16, 2019

Daryl DeFord. Introduction to discrete markov chain monte carlo for redistricting, June 16, 2019

work page 2019
[17]

Redistricting reform in Virginia: Districting criteria in context.Virginia Policy Review, XII:120–146, Spring 2019

Daryl DeFord and Moon Duchin. Redistricting reform in Virginia: Districting criteria in context.Virginia Policy Review, XII:120–146, Spring 2019

work page 2019
[18]

Recombination: A Family of Markov Chains for Redistricting.Harvard Data Science Review, 3(1), mar 31 2021

Daryl DeFord, Moon Duchin, and Justin Solomon. Recombination: A Family of Markov Chains for Redistricting.Harvard Data Science Review, 3(1), mar 31 2021

work page 2021
[19]

Sur la sph` ere vide

Boris Delaunay. Sur la sph` ere vide. a la m´ emoire de georges vorono¨ ı.Bulletin de l’Acad` emie des Sciences de l’Union des R` epubliques Sovi` etiques Socialistes. VII s` erie. Classe des sciences math` ematiques et naturelles, (6):793–800, 1934

work page 1934
[20]

The (homological) persistence of gerry- mandering.Foundations of Data Science, 4(4):581–622, 2022

Moon Duchin, Tom Needham, and Thomas Weighill. The (homological) persistence of gerry- mandering.Foundations of Data Science, 4(4):581–622, 2022

work page 2022
[21]

Moon Duchin and Douglas M. Spencer. Models, Race, and the Law.The Yale Law Journal, 130:744–797, 2021

work page 2021
[22]

Discrete geometry for electoral geography.arXiv preprint arXiv:1808.05860, 2023

Moon Duchin and Bridget Eileen Tenner. Discrete geometry for electoral geography.arXiv preprint arXiv:1808.05860, 2023. Version 2, revised August 2023

work page arXiv 2023
[23]

Empirical analysis of political districting splitability via uniform spanning trees in polynomial time.Scripps Senior Theses, 2025

Brooke Feinberg. Empirical analysis of political districting splitability via uniform spanning trees in polynomial time.Scripps Senior Theses, 2025. Available athttps://scholarship. claremont.edu/scripps_theses/2691

work page 2025
[24]

Automated redistrict- ing simulation using Markov chain Monte Carlo.Journal of Computational and Graphical Statistics, 29(4):715–728, 2020

Benjamin Fifield, Michael Higgins, Kosuke Imai, and Alexander Tarr. Automated redistrict- ing simulation using Markov chain Monte Carlo.Journal of Computational and Graphical Statistics, 29(4):715–728, 2020. 28

work page 2020
[25]

Random graph models for dual graphs.Scripps Senior Theses, 2025

Anne Friedman. Random graph models for dual graphs.Scripps Senior Theses, 2025. Available athttps://scholarship.claremont.edu/scripps_theses/2598

work page 2025
[26]

Mattingly

Gregory Herschlag, Han Sung Kang, Justin Luo, Christy Vaughn Graves, Sachet Bangia, Robert Ravier, and Jonathan C. Mattingly. Quantifying gerrymandering in North Carolina. Statistics and Public Policy, 7(1):452–479, 2020

work page 2020
[28]

Available athttps://arxiv.org/abs/1309.5413

work page arXiv
[29]

Sequential Monte Carlo for sampling balanced and compact redistricting plans.Annals of Applied Statistics, 17(4):3300–3323, 2023

Cory McCartan and Kosuke Imai. Sequential Monte Carlo for sampling balanced and compact redistricting plans.Annals of Applied Statistics, 17(4):3300–3323, 2023

work page 2023
[30]

Procaccia and Jamie Tucker-Foltz

Ariel D. Procaccia and Jamie Tucker-Foltz. Compact redistricting plans have many spanning trees.ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022

work page 2022
[31]

Spanning tree bounds for grid graphs.The Electronic Journal of Combina- torics, 31, 2024

Kristopher Tapp. Spanning tree bounds for grid graphs.The Electronic Journal of Combina- torics, 31, 2024

work page 2024
[32]

Political districting to minimize cut edges.Mathe- matical Programming Computation, 14:623–672, 2022

Hamidreza Validi and Austin Buchanan. Political districting to minimize cut edges.Mathe- matical Programming Computation, 14:623–672, 2022

work page 2022
[33]

Wilson.Graph Theory and Spanning Trees

Robin J. Wilson.Graph Theory and Spanning Trees. Longman Group Ltd, 4 edition, 1996

work page 1996
[34]

Number of spanning trees on a lattice.Journal of Physics A: Mathematical and General, 10(6):L113, jun 1977

F Y Wu. Number of spanning trees on a lattice.Journal of Physics A: Mathematical and General, 10(6):L113, jun 1977

work page 1977
[35]

Mathematically quantifying non-responsiveness of the 2021 Georgia Congressional districting plan

Zhanzhan Zhao, Cyrus Hettle, Swati Gupta, Jonathan Christopher Mattingly, Dana Randall, and Gregory Joseph Herschlag. Mathematically quantifying non-responsiveness of the 2021 Georgia Congressional districting plan. InEquity and Access in Algorithms, Mechanisms, and Optimization, EAAMO ’22. Association for Computing Machinery, 2022. 29

work page 2021