Tightening curves and graphs on surfaces

Chang, Hsien-Chih

Permalink

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

Description

Title

Tightening curves and graphs on surfaces

Author(s)

Chang, Hsien-Chih

Issue Date

2018-07-03

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

Erickson, Jeff

Doctoral Committee Chair(s)

Erickson, Jeff

Committee Member(s)

• Chekuri, Chandra
• Dunfield, Nathan M.
• Eppstein, David
• Kolla, Alexandra

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)

• curves
• graphs
• surfaces
• tightening
• homotopy
• electrical transformations
• Delta-Y transformations
• plane graphs
• smoothings
• graph minors
• medial
• monotonic
• untangling

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.

Graduation Semester

2018-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/101519

Copyright and License Information

Copyright 2018 by Hsien-Chih Chang

Owning Collections