Graph partitioning: redistricting games and the spherical zoning problem

In this dissertation we study problems related to graph partitioning, the process of dividing vertices of a graph into parts.Our motivating application is political redistricting, the redrawing of congressional voting district lines after each United States census. Redistricting can be formulated as a graph partitioning problem with population balance and geographical connectivity constraints. First, we study redistricting as a two-player game, where the players are the two major political parties. We introduce a new redistricting game, called the bisection protocol, and evaluate its ability to produce fair maps despite selfish play from both players. We also contribute new theoretical and empirical analyses of two previously suggested redistricting games: the I-cut-you-freeze protocol and the define-combine procedure. Next, we consider a graph-theoretic problem inspired by the bisection protocol. Given an undirected graph, can we repeatedly find and contract a perfect matching, terminating with a single vertex? We call this sequence of perfect matchings a perfect hierarchical matching (PHM), and we solve the problem of recognizing whether a graph has a PHM for several graph families. Finally, we consider the spherical zoning problem, a 3D graph partitioning variant in which vertices correspond to convex polytope cells in some volume, and we require a partition of the cells such that each part's surface is topologically equivalent to a sphere. Inspired by a similar tool for planar graph partitioning, we develop the 3D geo-graph, a dynamic data structure that supports efficient local search for the spherical zoning problem.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Ludden, Ian G.

Contributors dc:contributor

• Jacobson, Sheldon H.
• Chandrasekaran, Karthekeyan
• King, Douglas M.
• Mehta, Ruta
• Buchanan, Austin L.

• Graph Partitioning
• Political Redistricting
• Algorithmic Game Theory
• Combinatorial Optimization

Statement dc:rights

• (c) Ian Griffith Ludden

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121329

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121329