Files in this item



application/pdfCHANG-DISSERTATION-2018.pdf (4MB)
(no description provided)PDF


Title:Tightening curves and graphs on surfaces
Author(s):Chang, Hsien-Chih
Director of Research:Erickson, Jeff
Doctoral Committee Chair(s):Erickson, Jeff
Doctoral Committee Member(s):Chekuri, Chandra; Dunfield, Nathan M.; Eppstein, David; Kolla, Alexandra
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
electrical transformations
Delta-Y transformations
plane graphs
graph minors
Abstract:Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those with minimum number of self-intersections. While such operations and the tightening process has been studied extensively, surprisingly little is known about the quantitative bounds on the number of homotopy moves required to tighten an arbitrary curve. An unexpected connection exists between homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in statistical mechanics, robotics, and quantum mechanics. Steinitz, in his study of 3-dimensional polytopes, looked at the electrical transformations through the lens of medial construction, and implicitly established the connection to homotopy moves; later the same observation has been discovered independently in the context of knots. In this thesis, we study the process of tightening curves on surfaces using homotopy moves and their consequences on electrical transformations from a quantitative perspective. To derive upper and lower bounds we utilize tools like curve invariants, surface theory, combinatorial topology, and hyperbolic geometry. We develop several new tools to construct efficient algorithms on tightening curves and graphs, as well as to present examples where no efficient algorithm exists. We then argue that in order to study electrical transformations, intuitively it is most beneficial to work with monotonic homotopy moves instead, where no new crossings are created throughout the process; ideas and proof techniques that work for monotonic homotopy moves should transfer to those for electrical transformations. We present conjectures and partial evidence supporting the argument.
Issue Date:2018-07-03
Rights Information:Copyright 2018 by Hsien-Chih Chang
Date Available in IDEALS:2018-09-27
Date Deposited:2018-08

This item appears in the following Collection(s)

Item Statistics