{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121329"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121329","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Graph partitioning: redistricting games and the spherical zoning problem","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","abstract_has_math":false,"creators":["Ludden, Ian G."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Jacobson, Sheldon H.","Chandrasekaran, Karthekeyan","King, Douglas M.","Mehta, Ruta","Buchanan, Austin L."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Graph Partitioning","Political Redistricting","Algorithmic Game Theory","Combinatorial Optimization"],"languages":["en","eng"],"rights":["(c) Ian Griffith Ludden"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121329","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jacobson, Sheldon H.","Chandrasekaran, Karthekeyan","King, Douglas M.","Mehta, Ruta","Buchanan, Austin L."]},{"key":"dc:creator","label":"Author","values":["Ludden, Ian G."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-07-06"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Partitioning","Political Redistricting","Algorithmic Game Theory","Combinatorial Optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["(c) Ian Griffith Ludden"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121329"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","The student, Ian Ludden, accepted the attached license on 2023-07-03 at 08:39.","The student, Ian Ludden, submitted this Dissertation for approval on 2023-07-03 at 08:47.","This Dissertation was approved for publication on 2023-07-06 at 08:59.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19501 on 2023-12-04 at 17:18:10","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Graph partitioning: redistricting games and the spherical zoning problem"]}]}],"canonical_facts":{"dc:contributor":["Jacobson, Sheldon H.","Chandrasekaran, Karthekeyan","King, Douglas M.","Mehta, Ruta","Buchanan, Austin L."],"dc:creator":["Ludden, Ian G."],"dc:date":["2023-08","2023-07-06"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","The student, Ian Ludden, accepted the attached license on 2023-07-03 at 08:39.","The student, Ian Ludden, submitted this Dissertation for approval on 2023-07-03 at 08:47.","This Dissertation was approved for publication on 2023-07-06 at 08:59.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19501 on 2023-12-04 at 17:18:10","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121329"],"dc:language":["en","eng"],"dc:rights":["(c) Ian Griffith Ludden"],"dc:subject":["Graph Partitioning","Political Redistricting","Algorithmic Game Theory","Combinatorial Optimization"],"dc:title":["Graph partitioning: redistricting games and the spherical zoning problem"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}