University of Illinois Urbana-Champaign

Graph partitioning: redistricting games and the spherical zoning problem

Ludden, Ian G.

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

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

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
Copyright and License Information
(c) Ian Griffith Ludden

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois