Graph partitioning: redistricting games and the spherical zoning problem

Ludden, Ian G.

Permalink

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

Description

Title

Graph partitioning: redistricting games and the spherical zoning problem

Author(s)

Ludden, Ian G.

Issue Date

2023-07-06

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon H.

Doctoral Committee Chair(s)

Jacobson, Sheldon H.

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• graph partitioning
• political redistricting
• algorithmic game theory
• combinatorial optimization

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

(c) Ian Griffith Ludden

Owning Collections